Finding a maximum independent set in a permutation graph
From MaRDI portal
Publication:916397
DOI10.1016/0020-0190(90)90180-6zbMATH Open0703.68062OpenAlexW2069038057MaRDI QIDQ916397FDOQ916397
Authors: Haklin Kim 
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(90)90180-6
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- A characterization of perfect graphs
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- Bipartite permutation graphs
- Title not available (Why is that?)
- Permutation Graphs and Transitive Graphs
- On Comparability and Permutation Graphs
- Finding minimum dominating cycles in permutation graphs
- Domination in permutation graphs
- On testing isomorphism of permutation graphs
- Title not available (Why is that?)
Cited In (12)
- The bottleneck independent domination on the classes of bipartite graphs and block graphs.
- Maximum weightk-independent set problem on permutation graphs
- On the ordered list subgraph embedding problems
- Bounds on 2-point set domination number of a graph
- MAXIMUM INDEPENDENT SET OF A PERMUTATION GRAPH IN K TRACKS
- Finding a maximum matching in a permutation graph
- Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
- On a graph partition problem with application to VLSI layout
- Complete edge-colored permutation graphs
- On approximating MIS over B1-VPG graphs*
- An efficient PRAM algorithm for maximum-weight independent set on permutation graphs
- Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
This page was built for publication: Finding a maximum independent set in a permutation graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q916397)
