A new approach for the domination problem on permutation graphs

DOI10.1016/0020-0190(91)90192-KzbMath0713.68038OpenAlexW2075703256MaRDI QIDQ750166

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)

Related Items

On the feedback vertex set problem in permutation graphs, Parallel algorithms on circular-arc graphs, A polynomial-time algorithm for the paired-domination problem on permutation graphs, An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs

Cites Work

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