Formulações e Algoritmos de Solução para o Conjunto Dominante 2-Conexo Mínimo
Autores
|
5588 |
Vinícius Leal do Forte
|
2095,519
|
|
5589 |
2095,519
|
Informações:
Publicações do PESC
Seja G = (V;E) um grafo não-direcionado com um conjunto de vértices V e um conjunto de arestas E. Associado a G, assuma que um conjunto não vazio W V é identificado e que este induz um subgrafo GW em G. W é denominado um conjunto dominante, se todo vértice de G pertence a W ou tem um vizinho em W. Por sua vez, quando GW é 2-aresta (resp. 2-vértice) conexo o conjunto dominante W é dito 2-aresta (resp. 2-vértice) conexo. Em vários contextos, teóricos ou práticos, encontrar um conjunto dominante 2-{aresta,vértice} conexo de mínima cardinalidade é do especial interesse, sendo este o tema desta tese. Antes de nossa investigação, nenhuma formulação ou algoritmo de solução exata existia para o problema, na literatura. Aqui, introduzimos sete formulações, para ele e algoritmos de solução exata baseados nessas formulações. Além disso, duas heurísticas primais são também propostas e testadas nesta tese. Da mesma forma, comparações analíticas e computacionais foram conduzidas para as formulações e experimentos computacionais foram efetuados para testar os algoritmos de solução. Como resultado de nossa investigação, instâncias do problema definidas sobre grafos com até 200 vértices foram resolvidos à otimalidade.
Let G = (V;E) be an undirected graph with a set of vertices V and a set of edges E. Assuming that a non empty set W V is given, let GW be the subgraph it induces in G. W is called a dominating set if every vertex of G belongs to W or has a neighbor vertex in that set. Additionally, if GW is 2-edge (resp. 2-vertex) connected, the dominating set W is called 2-edge (resp. 2-vertex) connected. In various contexts, practical or theoretical, it is particularly interesting to finding a 2-{edge,vertex} connected dominating set with a cardinality as small as possible, and that is precisely the subject of this thesis. Prior to our investigation, no formulation or exact solution algorithm was found in the literature for the problem. Here, seven different formulations are introduced for it, together with corresponding exact solution algorithms. Furthermore, two primal heuristic are also investigated . Likewise, analytical and computational comparisons are carried out among our formulations while computational experiments were implemented to test the solution algorithms. As a result of our investigation, problem instances defined over graphs with as many as 200 vertices were solved to proven optimality.