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

DOI10.1016/j.ejc.2011.10.011zbMath1257.05118OpenAlexW2173544181MaRDI QIDQ1933642

E. Lappas, Leonidas Palios, Stavros D. Nikolopoulos

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) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (10)

Computing a minimum paired-dominating set in strongly orderable graphs ⋮ Complexity of paired domination in AT-free and planar graphs ⋮ A linear-time algorithm for weighted paired-domination on block 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 ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ Paired Domination in Graphs ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes

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