A polynomial-time algorithm for the paired-domination problem on permutation graphs

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

zbMATH Keywords

algorithmpermutation graphpaired-domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

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