A polynomial-time algorithm for the paired-domination problem on permutation graphs
From MaRDI portal
Publication:1003667
DOI10.1016/j.dam.2008.02.015zbMath1168.05366MaRDI QIDQ1003667
Cheng, T. C. Edwin, Erfang Shan, Li-ying Kang
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
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs, Linear-time algorithm for the paired-domination problem in convex bipartite 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, Hardness results and approximation algorithms for (weighted) paired-domination in graphs, Complexity of distance paired-domination problem in 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, Linear-time algorithm for the matched-domination problem in cographs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Transitive Orientation of Graphs and Identification of Permutation Graphs
