Finding maximum cliques on circular-arc graphs

DOI10.1016/0020-0190(87)90007-XzbMath0654.68082OpenAlexW2113796189MaRDI QIDQ1108807

Alberto Apostolico, Susanne E. Hambrusch

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90007-x

zbMATH Keywords

cliquecircular-arc graph

Mathematics Subject Classification ID

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

Related Items

An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs ⋮ A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle ⋮ Two remarks on circular arc graphs ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Paths in interval graphs and circular arc graphs ⋮ Optimal parallel algorithms on circular-arc graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Preserving order in a forest in less than logarithmic time and linear space
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• The NP-completeness column: an ongoing guide