An O(n)-time algorithm for the paired domination problem on permutation graphs
DOI10.1016/J.EJC.2011.10.011zbMATH Open1257.05118OpenAlexW2173544181MaRDI QIDQ1933642FDOQ1933642
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
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
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)
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
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- Permutation bigraphs and interval containments
- Paired domination in graphs
- Leaf sector covers with applications on circle 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1933642)
