Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
From MaRDI portal
Publication:3791188
DOI10.1137/0217032zbMath0647.05048OpenAlexW1981303423MaRDI QIDQ3791188
Alessandro D'Atri, Marina Moscarini
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217032
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph theory (05C99)
Related Items
Alternating cycle-free matchings ⋮ Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ On the terminal connection problem ⋮ Dominating cliques in distance-hereditary graphs ⋮ Reconstruction of distance hereditary 2-connected graphs ⋮ Weighted efficient domination problem on some perfect graphs ⋮ Hamilton cycles in almost distance-hereditary graphs ⋮ Connected domination and steiner set on asteroidal triple-free graphs ⋮ Powers of distance-hereditary graphs ⋮ Injective hulls of various graph classes ⋮ Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs ⋮ On edge perfectness and classes of bipartite graphs ⋮ Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy ⋮ Traceability of connected domination critical graphs ⋮ Networks with small stretch number ⋮ Steiner 4-diameter, maximum degree and size of a graph ⋮ Enumeration and maximum number of minimal connected vertex covers in graphs ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Homogeneously orderable graphs ⋮ On the computational difficulty of the terminal connection problem ⋮ Unique response Roman domination: complexity and algorithms ⋮ Homogeneously orderable graphs and the Steiner tree problem ⋮ Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs ⋮ A note on connected dominating sets of distance-hereditary graphs ⋮ Efficient enumeration of non-isomorphic distance-hereditary graphs and related graphs ⋮ MAD trees and distance-hereditary graphs ⋮ Simple linear-time algorithms for counting independent sets in distance-hereditary graphs ⋮ LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs ⋮ Connected domination and Steiner set on weighted permutation graphs ⋮ Bipartite almost distance-hereditary graphs ⋮ Equistable distance-hereditary graphs ⋮ Graphs with bounded induced distance ⋮ Distance-hereditary comparability graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Distance-hereditary digraphs ⋮ The Hamiltonian problem on distance-hereditary graphs ⋮ Weighted connected \(k\)-domination and weighted \(k\)-dominating clique in distance-hereditary graphs ⋮ Domination in distance-hereditary graphs ⋮ Computing a metric basis of a 2-connected bipartite distance-hereditary graph ⋮ Connected Domination ⋮ Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs ⋮ A multivariate analysis of the strict terminal connection problem ⋮ Weighted connected domination and Steiner trees in distance-hereditary graphs ⋮ Computing a metric basis of a bipartite distance-hereditary graph ⋮ Minimum Eccentricity Shortest Paths in Some Structured Graph Classes ⋮ Laminar structure of ptolemaic graphs with applications ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Rebuilding convex sets in graphs ⋮ Eccentricity function in distance-hereditary graphs ⋮ ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES ⋮ On an edge partition and root graphs of some classes of line graphs ⋮ Fast and simple algorithms for counting dominating sets in distance-hereditary graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters
This page was built for publication: Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
