Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
Authors:
- Alessandro D’atriADAlessandro D’atri
- Marina MoscariniMMMarina Moscarini
- 1 June 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 17 (3) , 521-538
Abstract
Distance-hereditary graphs have been introduced by Howorka and studied in the literature with respect to their metric properties. In this paper several equivalent characterizations of these graphs are given: in terms of existence of particular kinds of vertices (isolated, leaves, twins) and in terms of properties of connections, separators, and hangings. Distance-hereditary graphs are then studied from the algorithmic viewpoint: simple recognition algorithms are given and it is shown that the problems of finding cardinality Steiner trees and connected dominating sets are polynomially solvable in a distance-hereditary graph.Keywords
This publication has 11 references indexed in Scilit:
- Chordality properties on graphs and minimal conceptual connections in semantic data modelsJournal of Computer and System Sciences, 1986
- Distance-hereditary graphsJournal of Combinatorial Theory, Series B, 1986
- The NP-completeness column: an ongoing guideJournal of Algorithms, 1985
- Clustering and domination in perfect graphsDiscrete Applied Mathematics, 1984
- Degrees of acyclicity for hypergraphs and relational database schemesJournal of the ACM, 1983
- Characterizations of strongly chordal graphsDiscrete Mathematics, 1983
- A characterization of ptolemaic graphsJournal of Graph Theory, 1981
- Complement reducible graphsDiscrete Applied Mathematics, 1981
- A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHSThe Quarterly Journal of Mathematics, 1977
- GRAPH THEORY1969