Permutation graphs: Connected domination and Steiner trees
From MaRDI portal
Publication:1174135
DOI10.1016/0012-365X(90)90359-PzbMath0744.05059OpenAlexW2039105018MaRDI QIDQ1174135
Charles J. Colbourn, Lorna K. Stewart
Publication date: 25 June 1992
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(90)90359-p
Related Items (32)
On the terminal connection problem ⋮ On the feedback vertex set problem in permutation graphs ⋮ On dominating set of some subclasses of string graphs ⋮ On domination problems for permutation and other graphs ⋮ Making a dominating set of a graph connected ⋮ Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy ⋮ The balanced connected subgraph problem for geometric intersection graphs ⋮ Traceability of connected domination critical graphs ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ On the computational difficulty of the terminal connection problem ⋮ Diametral path graphs ⋮ On the Structure of Graphs Vertex Critical with Respect to Connected Domination ⋮ \(H\)-domination in graphs ⋮ Dominating sets in perfect graphs ⋮ Problems with generalized Steiner problems ⋮ Edge domination on bipartite permutation graphs and cotriangulated graphs ⋮ Connected domination and Steiner set on weighted permutation graphs ⋮ Computing residual connectedness reliability for restricted networks ⋮ The complexity of domination problems in circle graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ 2-edge connected dominating sets and 2-connected dominating sets of a graph ⋮ A branch-and-cut algorithm for the maximum covering cycle problem ⋮ 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 ⋮ An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs ⋮ Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs ⋮ Finding minimum dominating cycles in permutation graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ CONNECTED LIAR'S DOMINATION IN GRAPHS: COMPLEXITY AND ALGORITHMS
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Domination, independent domination, and duality in strongly chordal graphs
- Clustering and domination in perfect graphs
- Complement reducible graphs
- Independent domination in chordal graphs
- A linear algorithm for the domination number of a series-parallel graph
- Steiner trees, partial 2–trees, and minimum IFI networks
- On the Algorithmic Complexity of Total Domination
- Steiner trees, connected domination and strongly chordal graphs
- On finding spanning eulerian subgraphs
- Domination in permutation graphs
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- Linear time transformations between combinatorial problems
- Dominating Sets in Chordal Graphs
- Transitive Orientation of Graphs and Identification of Permutation Graphs
This page was built for publication: Permutation graphs: Connected domination and Steiner trees
