Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications

DOI10.1142/S0129054197000288MaRDI QIDQ4385200zbMATH OpenFDO

Authors Glenn K. Manacher, Terrance A. Mankus

Publication date 25 May 1998

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054197000288

zbMATH Keywords

maximum cliqueproper circular arcs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
• Finding maximum cliques on circular-arc graphs
• An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs

Cited in

(8)

• Mutual exclusion scheduling with interval graphs or related classes. I
• On a circle placement problem
• Finding maximum cliques on circular-arc graphs
• An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
• scientific article; zbMATH DE number 3891419 (Why is no real title available?)
• Efficient algorithms for finding maximum cliques of an overlap graph
• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs

This page was built for publication: Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications

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