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

sweeping algorithmminimum-cardinality dominating set

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph algorithms (graph-theoretic aspects) (05C85) 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) Planar graphs; geometric and topological aspects of graph theory (05C10)

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

(15)

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