SIAM Journal on Computing · 1988 · 129 citations · 10 references
Natural SciencesMathematicsCombinatoricsComputational GeometryTopologyGeometric GraphsGraph AlgorithmsGraph TheoryMetric GeometryMetric Graph TheorySteiner Tree ProblemTree Algorithms
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.
10
Derek G. Corneil, H. Lerchs, L.Stewart Burlingham · Discrete Applied Mathematics · 1981 · 837 citations
Hans‐Jürgen Bandelt, Henry Martyn Mulder · Journal of Combinatorial Theory Series B · 1986 · 467 citations
Characterizations of strongly chordal graphs
Martin Farber · Discrete Mathematics · 1983 · 350 citations