Finding maximum cliques on circular-arc graphs

DOI10.1016/0020-0190(87)90007-XMaRDI QIDQ1108807zbMATH OpenOpenAlexFDO

Authors 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

circular-arc graphclique

Mathematics Subject Classification ID

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

Review text

An algorithm is presented that, given the intersection model S of a circular-arc graph G with n vertices and m edges, finds a maximum-sized clique of G in \(O(n^ 2 \log \log n)\) time. The previous best time bound for this problem was \(O(n^ 2 \log n+mn)\).

Recommendations

• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle
• scientific article; zbMATH DE number 3891419
• Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• Preserving order in a forest in less than logarithmic time and linear space
• The NP-completeness column: an ongoing guide

Cited in

(20)

• An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
• Efficient parallel recognition of some circular arc graphs. I
• Finding a maximum matching in a circular-arc graph
• Paths in interval graphs and circular arc graphs
• Optimal parallel algorithms on circular-arc graphs
• Maximum clique exhaustive search in circulant \(k\)-hypergraphs
• In-place algorithms for computing a largest clique in geometric intersection graphs
• Polynomial time algorithms on circular-arc overlap graphs
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• Stability in circular arc graphs
• scientific article; zbMATH DE number 19214 (Why is no real title available?)
• Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
• Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications
• A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
• Two remarks on circular arc graphs
• Computing maximum cliques in unit disk graphs
• In-place algorithms for computing a largest clique in geometric intersection graphs
• A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle

This page was built for publication: Finding maximum cliques on circular-arc graphs

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