Steiner trees, connected domination and strongly chordal graphs
From MaRDI portal
Publication:3701460
DOI10.1002/net.3230150109zbMath0579.05050OpenAlexW2153250924MaRDI QIDQ3701460
Kevin White, William R. Pulleyblank, Martin Farber
Publication date: 1985
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230150109
polynomial algorithmchordal graphsseries-parallel graphsSteiner tree problemsconnected dominating set problemsNP-completeness results
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)
Related Items (56)
A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs ⋮ A parallel algorithm for computing Steiner trees in strongly chordal graphs ⋮ The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets ⋮ The parallel solution of domination problems on chordal and strongly chordal graphs ⋮ On the terminal connection problem ⋮ Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs ⋮ Convexity in Graphs and Hypergraphs ⋮ Minimum-maximal matching in series-parallel graphs ⋮ Connected domination and steiner set on asteroidal triple-free graphs ⋮ The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs ⋮ The \(k\)-hop connected dominating set problem: hardness and polyhedra ⋮ Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage ⋮ THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS ⋮ Making a dominating set of a graph connected ⋮ A unified approach to domination problems on interval graphs ⋮ On hypergraph acyclicity and graph chordality ⋮ Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy ⋮ The balanced connected subgraph problem for geometric intersection graphs ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ Cooperative mobile guards in grids ⋮ Steiner trees for hereditary graph classes: a treewidth perspective ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ On the computational difficulty of the terminal connection problem ⋮ Parameterized complexity of multicut in weighted trees ⋮ P versus NPC: minimum Steiner trees in convex split graphs ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs ⋮ Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs ⋮ Steiner distance and convexity in graphs ⋮ Balanced substructures in bicolored graphs ⋮ Sequentially swapping tokens: further on graph classes ⋮ On bondage numbers of graphs: a survey with some comments ⋮ Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs ⋮ Dominating sets in perfect graphs ⋮ Permutation graphs: Connected domination and Steiner trees ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Problems with generalized Steiner problems ⋮ Connected domination and Steiner set on weighted permutation graphs ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ Complexity of distance paired-domination problem in graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Intersection graphs of non-crossing paths ⋮ Chordality properties on graphs and minimal conceptual connections in semantic data models ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ Complexity of Steiner Tree in Split Graphs - Dichotomy Results ⋮ 2-edge connected dominating sets and 2-connected dominating sets of a graph ⋮ Counting dominating sets in generalized series-parallel graphs ⋮ 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 ⋮ Revising Johnson's table for the 21st century ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters
Cites Work
This page was built for publication: Steiner trees, connected domination and strongly chordal graphs
