Problemas Separadores para Grafos de Caminho
Autores
|
3333 |
6,410
|
|
|
3334 |
6,410
|
Informações:
Publicações do PESC
Grafos de interseção são os grafos obtidos de uma família de conjuntos, associando-se a cada conjunto um vértice e, definindo-se que dois vértices são adjacentes se e somente se os conjuntos correspondentes têm interseção não vazia.
De interesse particular são os grafos cordais, que são os grafos de interseção de subárvores de uma árvore e os grafos de intervalo, que são os grafos de interseção de intervalos na reta real.
Examinamos neste trabalho outras classes de grafos de interseção: as classes dos grafos de caminho que são os grafos de interseção de caminhos em uma árvore. Quando a árvore for não direcionada, diremos que se trata de um grafo de caminho não direcionado, ou UV. Quando a árvore for direcionada ou direcionada e enraizada dizemos que se trata de um grafo DV ou RDV, respectivamente.
É sabido que INTERVALO C RDV c DV c UV C CORDAL.
Um problema de decisão é dito separador para A e B, B C A, se este problema é NP-Completo quando restrito a A mas é polinomial quando restrito a B.
Neste trabalho consideramos problemas separadores para grafos de caminho, isto é, problemas separadores em que pelo menos uma das classes envolvidas é de grafos de caminho. Estes problemas são: CONJUNTO DOMINANTE MÍNIMO, separador para UV e RDV; CLIQUE DOMINANTE MÍNIMO, separador para cordais e UV e CIRCUITO HAMILTONIANO, separador para DV e de intervalo.
Consideramos também o problema ISOMORFISMO DE GRAFOS que é I-Completo para grafos UV mas polinomial para grafos RDV.
Intersection graphs are those obtained from a family of sets, associating a vertex with each set of the family. Two vertices are adjacent if and only if the intersection of the corresponding sets is not empty.
Two classes of intersection graphs ai-e of special interest: chordal graphs and interval gi-aphs. The former are the intersection graphs of subtrees of a tree, while the latter are those for the intervals of a real line.
In this worlc we examine some other classes of intersection graphs: the classes of path graphs, which are the intersection graphs of paths of a tree.
When the tree is undirected we obtain an undirected path gi-aph, or UV. When the tree is directed or rooted directed then the corresponding graph is called DV or RDV, respectively.
It is known that INTERVAL C RDV C DV C UV C CHORDAL.
A decision problem is called separating for A and I?, I? C A, if it is NP-Complete when restricted to A, but polynomial for I?.
In this worlc we consider separating problems for path graphs, that is, separating problems in which at least one the classes involved is a path graph.
The problems are: MINIMUM DOMINATING SET, separating for UV and RDV; MINIMUM DOMINATING CLIQUE, separating for chordal and UV; and HAMILTONIAN CYCLE, separating for DV and interval.
We also consider the GRAPH ISOMORPHISM problern. It is Isomorphism-Complete for UV graphs, but polynomial for RDV.