Polynomial time algorithms on circular-arc overlap graphs

DOI10.1002/NET.3230210205zbMATH Open0722.90078OpenAlexW2026697373MaRDI QIDQ3211136FDOQ3211136

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

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

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)

Cites Work

• Title not available (Why is that?)

Cited In (6)

• Computing and counting longest paths on circular-arc graphs in polynomial time
• Maximum independent set and maximum clique algorithms for overlap graphs
• OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS
• Efficient algorithms for finding maximum cliques of an overlap graph
• Title not available (Why is that?)
• 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)