An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs

DOI10.1007/978-3-642-10217-2_36zbMath1267.05267OpenAlexW2160788672MaRDI QIDQ3651563

Stavros D. Nikolopoulos, Leonidas Palios, E. Lappas

Publication date: 11 December 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-10217-2_36

zbMATH Keywords

complexityalgorithmsdominationpermutation graphspaired-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 (7)

A linear-time algorithm for weighted paired-domination on block graphs ⋮ Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ A linear-time algorithm for paired-domination on circular-arc graphs ⋮ On the 12-representability of induced subgraphs of a grid graph

This page was built for publication: An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs