Steiner trees, connected domination and strongly chordal graphs

DOI10.1002/NET.3230150109zbMATH Open0579.05050OpenAlexW2153250924MaRDI QIDQ3701460FDOQ3701460

Authors: Kevin White, Martin Farber, William R. Pulleyblank 

Publication date: 1985

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230150109

Recommendations

• Doubly chordal graphs, steiner trees, and connected domination
• Permutation graphs: Connected domination and Steiner trees
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• Connected domination and Steiner set on weighted permutation graphs
• Steiner intervals in strongly chordal graphs

zbMATH Keywords

chordal graphspolynomial algorithmseries-parallel graphsSteiner tree problemsconnected dominating set problemsNP-completeness results

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Cites Work

• Title not available (Why is that?)
• Totally-Balanced and Greedy Matrices

Cited In (67)

• Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
• Counting dominating sets in generalized series-parallel graphs
• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Balanced substructures in bicolored graphs
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• P versus NPC: minimum Steiner trees in convex split graphs
• Title not available (Why is that?)
• On convexity in split graphs: complexity of Steiner tree and domination
• Open packing in \(H\)-free graphs and subclasses of split graphs
• Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs
• Problems with generalized Steiner problems
• On the terminal connection problem
• Minimum-maximal matching in series-parallel graphs
• Permutation graphs: Connected domination and Steiner trees
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy
• Labeling algorithms for domination problems in sun-free chordal graphs
• On the computational difficulty of the terminal connection problem
• Parameterized complexity of multicut in weighted trees
• Weighted connected domination and Steiner trees in distance-hereditary graphs
• Paired-domination problem on distance-hereditary graphs
• A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
• Bibliography on domination in graphs and some basic definitions of domination parameters
• On hypergraph acyclicity and graph chordality
• Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs
• Strong elimination ordering of the total graph of a tree
• Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
• Complexity of Steiner tree in split graphs -- dichotomy results
• Total domination, connected vertex cover and Steiner tree with conflicts
• Cooperative mobile guards in grids
• Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
• Steiner intervals in strongly chordal graphs
• Complexity of distance paired-domination problem in graphs
• Domination, independent domination, and duality in strongly chordal graphs
• A multivariate analysis of the strict terminal connection problem
• Connected domination and Steiner set on weighted permutation graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Dominating sets in perfect graphs
• Intersection graphs of non-crossing paths
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
• The \(k\)-hop connected dominating set problem: hardness and polyhedra
• Steenrod problem and the domination relation
• Making a dominating set of a graph connected
• Steiner trees for hereditary graph classes: a treewidth perspective
• On bondage numbers of graphs: a survey with some comments
• Chordality properties on graphs and minimal conceptual connections in semantic data models
• The balanced connected subgraph problem for geometric intersection graphs
• The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
• Steiner distance and convexity in graphs
• A parallel algorithm for computing Steiner trees in strongly chordal graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• A linear-time algorithm for semitotal domination in strongly chordal graphs
• THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS
• 2-edge connected dominating sets and 2-connected dominating sets of a graph
• Doubly chordal graphs, steiner trees, and connected domination
• Convexity in Graphs and Hypergraphs
• The parallel solution of domination problems on chordal and strongly chordal graphs
• A unified approach to domination problems on interval graphs
• Connected domination and steiner set on asteroidal triple-free graphs
• Sequentially swapping tokens: further on graph classes
• Connected domination
• Revising Johnson's table for the 21st century
• On Steiner trees and minimum spanning trees in hypergraphs
• The \(k\)-hop connected dominating set problem: approximation and hardness
• Representations of graphs and networks (coding, layouts and embeddings)

This page was built for publication: Steiner trees, connected domination and strongly chordal graphs

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