A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs

DOI10.1137/S0895480192242754MaRDI QIDQ4881292zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

algorithmmaximum weight cliquecircular arcsproper circular arc graph\(q\)-coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

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)