A new approach for the domination problem on permutation graphs

DOI10.1016/0020-0190(91)90192-KMaRDI QIDQ750166zbMATH OpenOpenAlexFDO

Authors D. Kharzeev

Publication date 1991

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90192-k

zbMATH Keywords

algorithm analysispermutation graphminimum weight dominating set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On domination problems for permutation and other graphs
• scientific article; zbMATH DE number 3943870
• Domination in permutation graphs
• An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• Fast algorithms for the dominating set problem on permutation graphs
• An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
• An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
• On the domination number of permutation graphs and an application to strong fixed points

Cites work

• A Linear Recognition Algorithm for Cographs
• An efficient algorithm for maxdominance, with applications
• Bipartite permutation graphs
• Domination in permutation graphs
• Finding a minimum independent dominating set in a permutation graph
• On Comparability and Permutation Graphs
• The edge inducibility of graphs
• The minimum weight dominating set problem for permutation graphs is in NC
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(14)

• scientific article; zbMATH DE number 4049081 (Why is no real title available?)
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• Parallel algorithms on circular-arc graphs
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Connected domination and Steiner set on weighted permutation graphs
• scientific article; zbMATH DE number 3943870 (Why is no real title available?)
• Finding a minimum independent dominating set in a permutation graph
• Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs
• On the feedback vertex set problem in permutation graphs
• An efficient algorithm for maxdominance, with applications
• An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
• On the broadcast domination number of permutation graphs
• Domination in permutation graphs
• The minimum weight dominating set problem for permutation graphs is in NC

This page was built for publication: A new approach for the domination problem on permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q750166)