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

DOI10.1007/978-3-642-10217-2_36MaRDI QIDQ3651563zbMATH OpenOpenAlexFDO

Authors E. Lappas, Stavros D. Nikolopoulos, Leonidas Palios

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

algorithmscomplexitydominationpermutation graphspaired-domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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
• An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs
• Algorithmic aspects of paired disjunctive domination in graphs
• A new approach for the domination problem on permutation graphs
• Fast algorithms for the dominating set problem on permutation graphs
• An O(N + M)-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• Algorithm of acyclic dominating set problem on bipartite permutation graphs

Cited in

(12)

• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• On the 12-representability of induced subgraphs of a grid graph
• An optimal algorithm to find minimum k-hop dominating set of interval graphs
• An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
• An optimal algorithm for computing minimum k-hop dominating set of permutation graphs
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Paired domination on interval and circular-arc graphs
• A linear-time algorithm for weighted paired-domination on block graphs
• A linear-time algorithm for paired-domination on circular-arc graphs
• Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
• A new approach for the domination problem on permutation graphs
• An optimal algorithm to find minimum k-hop connected dominating set of permutation 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 Q3651563)