A new approach for the domination problem on permutation graphs
From MaRDI portal
Publication:750166
DOI10.1016/0020-0190(91)90192-KzbMATH Open0713.68038OpenAlexW2075703256MaRDI QIDQ750166FDOQ750166
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
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Bipartite permutation graphs
- Finding a minimum independent dominating set in a permutation graph
- On Comparability and Permutation Graphs
- A Linear Recognition Algorithm for Cographs
- Domination in permutation graphs
- The edge inducibility of graphs
- An efficient algorithm for maxdominance, with applications
- The minimum weight dominating set problem for permutation graphs is in NC
Cited In (14)
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Connected domination and Steiner set on weighted permutation graphs
- 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)
