1988/06/01 by Alessandro D’Atri, Marina Moscarini · 129 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Cardinality (data modeling) #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Mathematics #Simple (philosophy) #Steiner tree problem
paper · doi:10.1137/0217032
published in SIAM Journal on Computing 17(3), 521-538 (Society for Industrial and Applied Mathematics)
openalex publication_date 1988/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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.