Algoritmos para o problema do subgrafo acíclico máximo sob restrições disjuntivas
2014
Neste trabalho sao abordados os problemas do Subgrafo Aciclico Maximo sob Restri coes Disjuntivas Negativas (SAMRDN) e Subgrafo Aciclico Maximo sob Restricoes Disjuntivas Positivas (SAMRDP), ambos pertencentes a classe NPDificil. Dado um certo par de entidades, para as restricoes disjuntivas negativas, no maximo uma delas podera compor uma solucao viavel. Ja para as restricoes disjuntivas positivas, dado um par de entidades, pelo menos uma delas devera compor uma solucao viavel. Os problemas SAMRDN e SAMRDP possuem como instância um grafo direcionado G = (V;A) e um grafo nao direcionado G = (A;E), que representa as restricoes disjuntivas, positivas ou negativas, sob pares de arcos do grafo G. SAMRDN consiste em determinar um subconjunto maximo A0 A para o qual o subgrafo G0 = (V;A0) seja aciclico e A0 seja um conjunto de vertices em G tal que nao existam arestas entre dois de seus vertices, ou seja, um conjunto independente em G. SAMRDP consiste em determinar um subconjunto maximo A0 A para o qual o subgrafo G0 = (V;A0) seja aciclico e A0 seja um conjunto de vertices em G tal que toda aresta em E seja incidente em algum vertice de A0, ou seja, uma cobertura por vertices em G. E provado que o problema de decisao sobre a viabilidade de SAMRDP e NP Completo, por uma reducao a partir do problema classico de Cobertura por Vertices. Para SAMRDN, sao apresentados seis algoritmos com fator de aproximacao constante igual a 1=2 para classes especiais de grafos de restricoes, tal que o calculo de um conjunto independente maximo em G seja polinomial. Dentre os seis algoritmos, tres deles seguindo a abordagem denominada late geram solucoes com no minimo a mesma cardinalidade das obtidas com os algoritmos equivalentes, segundo a abordagem early. E proposto um pre-processamento de instâncias para SAMRDN e SAMRDP. Testes experimentais sobre modelos de programacao linear inteira dos problemas sugerem que, ao se realizar o pre-processamento, solucoes melhores sao obtidas, no mesmo tempo de execucao. E tambem apresentado um procedimento de melhoria sobre uma solucao inicial de SAMRDN, obtida heuristicamente, que e entao vinculado a uma metaheur istica como um metodo de busca local. Resultados computacionais evidenciam que, para instâncias em que jV j > 200, a heuristica e preferivel a resolucao do modelo de programacao inteira por um software comercial.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI