A polynomial-time algorithm for the paired-domination problem on permutation graphs
From MaRDI portal
Publication:1003667
DOI10.1016/j.dam.2008.02.015zbMath1168.05366OpenAlexW2012682579MaRDI QIDQ1003667
Erfang Shan, Li-ying Kang, Cheng, T. C. Edwin
Publication date: 4 March 2009
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10397/479
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (15)
A linear-time algorithm for weighted paired-domination on block graphs ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ Total domination versus paired-domination in regular graphs ⋮ A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph ⋮ Graphs with maximum size and given paired-domination number ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Complexity of distance paired-domination problem in graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ An upper bound on the paired-domination number in terms of the number of edges in the graph ⋮ A linear-time algorithm for paired-domination problem in strongly chordal graphs ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Hardness results and approximation algorithms for (weighted) paired-domination in graphs ⋮ A linear-time algorithm for paired-domination on circular-arc graphs
Cites Work
- Paired-domination in inflated graphs
- Paired-domination in claw-free cubic graphs
- A new approach for the domination problem on permutation graphs
- Acyclic domination on bipartite permutation graphs
- Graphs with large paired-domination number
- Dominating direct products of graphs
- Vertices contained in all or in no minimum paired-dominating set of a tree
- Connected domination and Steiner set on weighted permutation graphs
- An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
- Total and paired-domination numbers of a tree
- Paired-domination of trees
- Fast algorithms for the dominating set problem on permutation graphs
- Paired domination on interval and circular-arc graphs
- Characterizations of trees with equal paired and double domination numbers
- An efficient PRAM algorithm for maximum-weight independent set on permutation graphs
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Paired-domination of Cartesian products of graphs and rainbow domination
- On Comparability and Permutation Graphs
- Domination in permutation graphs
- Paired-domination
- Some Efficient Algorithms for Permutation Graphs
- Paired-domination in graphs
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A polynomial-time algorithm for the paired-domination problem on permutation graphs
