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

maximum cliqueindependent setpolynomial-time algorithmscircular-arc overlap graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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)

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