Polynomial time algorithms on circular-arc overlap graphs

DOI10.1002/NET.3230210205MaRDI QIDQ3211136zbMATH OpenOpenAlexFDO

Authors Toshinobu Kashiwabara, Sumio Masuda, Kazuo Nakajima, Toshio Fujisawa

Publication date 1991

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230210205

zbMATH Keywords

circular-arc overlap graphsindependent setmaximum cliquepolynomial-time algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Maximum independent set and maximum clique algorithms for overlap graphs
• Independent Sets in Circular-Arc Graphs
• Efficient algorithms for finding maximum cliques of an overlap graph
• scientific article; zbMATH DE number 140476
• Finding maximum cliques on circular-arc graphs

Cited in

(6)

• Maximum independent set and maximum clique algorithms for overlap graphs
• Computing and counting longest paths on circular-arc graphs in polynomial time
• OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS
• Efficient algorithms for finding maximum cliques of an overlap graph
• scientific article; zbMATH DE number 6829367 (Why is no real title available?)
• A constant factor approximation algorithm for boxicity of circular arc graphs

This page was built for publication: Polynomial time algorithms on circular-arc overlap graphs

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