Finding a maximum independent set in a permutation graph

DOI10.1016/0020-0190(90)90180-6zbMath0703.68062OpenAlexW2069038057MaRDI QIDQ916397

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

zbMATH Keywords

independent setcliquepermutation graph

Mathematics Subject Classification ID

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

Related Items (10)

On the ordered list subgraph embedding problems ⋮ On approximating MIS over B1-VPG graphs* ⋮ Complete edge-colored permutation graphs ⋮ Bounds on 2-point set domination number of a graph ⋮ The bottleneck independent domination on the classes of bipartite graphs and block graphs. ⋮ 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 ⋮ Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs ⋮ Maximum weightk-independent set problem on permutation graphs ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding minimum dominating cycles in permutation graphs
• Bipartite permutation graphs
• A characterization of perfect graphs
• On Comparability and Permutation Graphs
• Domination in permutation graphs
• On testing isomorphism of permutation graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Permutation Graphs and Transitive Graphs

This page was built for publication: Finding a maximum independent set in a permutation graph