An O(n)-time algorithm for the paired domination problem on permutation graphs

DOI10.1016/J.EJC.2011.10.011MaRDI QIDQ1933642zbMATH OpenOpenAlexFDO

Authors E. Lappas, Stavros D. Nikolopoulos, Leonidas Palios

Publication date 24 January 2013

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2011.10.011

zbMATH Keywords

minimum-cardinality dominating setsweeping algorithm

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• A linear-time algorithm for paired-domination on circular-arc graphs
• Labelling algorithms for paired-domination problems in block and interval graphs
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs

Cited in

(16)

• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• Computing a minimum paired-dominating set in strongly orderable graphs
• Paired-domination problem on distance-hereditary graphs
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• Complexity of paired domination in AT-free and planar graphs
• A linear-time algorithm for weighted paired-domination on block graphs
• Algorithmic aspects of upper paired-domination in graphs
• Paired domination on interval and circular-arc graphs
• Paired domination in graphs
• An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
• Permutation bigraphs and interval containments
• Complexity of paired domination in at-free and planar graphs
• Linear-time algorithm for paired-domination on distance-hereditary graphs
• Leaf sector covers with applications on circle graphs
• Paired domination on supergrid graphs: NP-completeness, restricted pairings, and tight bounds
• A new approach for the domination problem on permutation graphs

This page was built for publication: An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs

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