An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
From MaRDI portal
Publication:3651563
DOI10.1007/978-3-642-10217-2_36zbMath1267.05267MaRDI 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
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
An optimal algorithm to find minimum k-hop dominating set of interval graphs, An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs, Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs, Linear-time algorithm for the paired-domination problem in convex bipartite graphs, On the 12-representability of induced subgraphs of a grid graph, A linear-time algorithm for weighted paired-domination on block graphs, A linear-time algorithm for paired-domination on circular-arc graphs