A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs

DOI10.1002/(SICI)1097-0037(199805)31:3%3C177::AID-NET4%3E3.0.CO;2-CzbMATH Open0990.05116OpenAlexW2059518216MaRDI QIDQ4540045FDOQ4540045

Authors: Andreas Brandstädt, Feodor F. Dragan 

Publication date: 21 July 2002

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199805)31:3%3C177::aid-net4%3E3.0.co;2-c

Recommendations

• Weighted connected domination and Steiner trees in distance-hereditary graphs
• A note on connected dominating sets of distance-hereditary graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
• Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs

zbMATH Keywords

Steiner treeconnected dominationlabeling algorithmdistance-hereditary graph

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Cited In (30)

• MAD trees and distance-hereditary graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Graphs with bounded induced distance
• Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
• A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
• Linear rank-width of distance-hereditary graphs
• The parameterized complexity of terminal monitoring set
• Weighted connected domination and Steiner trees in distance-hereditary graphs
• A note on connected dominating sets of distance-hereditary graphs
• Dominating cliques in distance-hereditary graphs
• The Weisfeiler-Leman dimension of distance-hereditary graphs
• Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs
• Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs
• On the clique-width of some perfect graph classes
• Homogeneously orderable graphs
• Networks with small stretch number
• Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)
• Steiner trees for hereditary graph classes: a treewidth perspective
• Equistable distance-hereditary graphs
• Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
• Weighted efficient domination problem on some perfect graphs
• Title not available (Why is that?)
• Domination in distance-hereditary graphs
• Structural parameters, tight bounds, and approximation for \((k, r)\)-center
• Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
• Laminar structure of ptolemaic graphs with applications
• The Hamiltonian problem on distance-hereditary graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Distance-hereditary comparability graphs
• The \(k\)-hop connected dominating set problem: approximation and hardness

This page was built for publication: A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4540045)