Several graph problems (e.g., steiner tree, connected domination, hamiltonian path, and iso- morphism problem), which can be solved in polynomial time for distance-hereditary graphs, are NP-complete or open for parity graphs. Moreover, the metric characterizations of these two graph classes suggest an excessive gap between them. We introduce a family of classes forming an innite lattice with respect to inclusion, whose bottom and top elements are the class of the distance-hereditary graphs and the class of the parity graphs, respectively. We propose this family as a reference framework for studying the computational complexity of fundamental graph prob- lems. For this purpose we characterize these classes using Cunningham decomposition and then use the devised structural characterization in order to show ecient algorithms for the recogni- tion and isomorphism problems. As far as the isomorphism graph problem is concerned we nd ecient algorithms for an innite number of dierent classes (forming a chain with respect to the inclusion relation) in the family.

Graph classes between parity and distance-hereditary graphs

CICERONE, SERAFINO;DI STEFANO, GABRIELE
1999

Abstract

Several graph problems (e.g., steiner tree, connected domination, hamiltonian path, and iso- morphism problem), which can be solved in polynomial time for distance-hereditary graphs, are NP-complete or open for parity graphs. Moreover, the metric characterizations of these two graph classes suggest an excessive gap between them. We introduce a family of classes forming an innite lattice with respect to inclusion, whose bottom and top elements are the class of the distance-hereditary graphs and the class of the parity graphs, respectively. We propose this family as a reference framework for studying the computational complexity of fundamental graph prob- lems. For this purpose we characterize these classes using Cunningham decomposition and then use the devised structural characterization in order to show ecient algorithms for the recogni- tion and isomorphism problems. As far as the isomorphism graph problem is concerned we nd ecient algorithms for an innite number of dierent classes (forming a chain with respect to the inclusion relation) in the family.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/6811
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 10
social impact