Weighted connected domination and Steiner trees in distance-hereditary graphs
type: Item
instance of: scholarly article
title: Weighted connected domination and Steiner trees in distance-hereditary graphs
zbMATH Open document ID: 0906.05030
DOI: 10.1016/S0166-218X(98)00060-2
author: Hong-Gwa Yeh
author: Gerard Jennhwa Chang
published in: Discrete Applied Mathematics
publication date: 1999-02-01T00:00:00Z
full work available at URL: dam
review text: A distance-hereditary graph is a connected graph in which every induced path is isometric, that is, the distance between any two vertices in an induced path equals their distance in the graph. A dominating set of a graph is a set of vertices such that every vertex outside is adjacent to a vertex in the set. The connected domination problem is to find a smallest connected dominating set. The Steiner tree problem is, for a given set \(T\) of target vertices, to find a smallest set \(S\) of vertices such that \(S \cup T\) is connected. Both problems are NP-complete in general. Restricted to distance-hereditary graphs they become solvable in linear time, even if we allow real weights on the vertices. This generalizes earlier work by \textit{A. Brandstädt} and \textit{F. F. Dragan} [Networks 31, No. 3, 177-182 (1998)].
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1218480
zbMATH Keywords: distance-hereditary graph
zbMATH Keywords: connected domination
zbMATH Keywords: Steiner tree
zbMATH Keywords: linear time algorithm
MaRDI profile type: Publication
cites work: Linear time algorithms for NP-hard problems restricted to partial k- trees
cites work: Distance-hereditary graphs
cites work: A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
cites work: Q3222874
cites work: Labeling algorithms for domination problems in sun-free chordal graphs
cites work: Weighted independent perfect domination on cocomparability graphs
cites work: Permutation graphs: Connected domination and Steiner trees
cites work: Complement reducible graphs
cites work: Clustering and domination in perfect graphs
cites work: A Linear Recognition Algorithm for Cographs
cites work: Dominating sets in perfect graphs
cites work: The traveling salesman problem on a graph and some related integer polyhedra
cites work: Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
cites work: Q3795243
cites work: Steiner Distance-Hereditary Graphs
cites work: Q4693383
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Q4198056
cites work: Completely separable graphs
cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
cites work: The Steiner tree problem
cites work: The NP-completeness column: an ongoing guide
cites work: Q3791195
cites work: The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
cites work: On finding spanning eulerian subgraphs
cites work: The node-weighted steiner tree problem
cites work: R -Domination in Graphs
cites work: Steiner trees, partial 2–trees, and minimum IFI networks
cites work: Steiner trees, connected domination and strongly chordal graphs
Wikidata QID: Q126777906
Recommended article: Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
Recommended article: Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
Recommended article: Connected domination and Steiner set on weighted permutation graphs
Recommended article: A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
Recommended article: Steiner trees, connected domination and strongly chordal graphs
Recommended article: Q4532748
Recommended article: A note on connected dominating sets of distance-hereditary graphs
Recommended article: Improved methods for approximating node weighted Steiner trees and connected dominating sets.
Recommended article: Q4247267
Recommended article: Steiner Distance-Hereditary Graphs
description: scientific article; zbMATH DE number 1218480