A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
DOI10.1137/S0895480192242754zbMATH Open0854.05092OpenAlexW2066204507MaRDI QIDQ4881292FDOQ4881292
Authors: Binay Bhattacharya, Jing Huang, Pavol Hell 
Publication date: 22 January 1997
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480192242754
Recommendations
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- scientific article; zbMATH DE number 3891419
- An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
- AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
- Finding maximum cliques on circular-arc graphs
- A maximum weight clique algorithm for dense circle graphs with many shared endpoints
- Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications
- A linear-time algorithm for clique-coloring problem in circular-arc graphs
- A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle
- Maximum weight independent set of circular-arc graph and its application
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cited In (10)
- Mutual exclusion scheduling with interval graphs or related classes. I
- A classification of locally semicomplete digraphs
- Clique-coloring circular-arc graphs
- An O(qn) algorithm to q-color a proper family of circular arcs
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
- A surprising permanence of old motivations (a not-so-rigid story)
- Two remarks on circular arc graphs
- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
- A linear-time algorithm for clique-coloring problem in circular-arc graphs
- Two cases of polynomial-time solvability for the coloring problem
This page was built for publication: A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4881292)
