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

DOI10.1137/S0895480192242754zbMath0854.05092OpenAlexW2066204507MaRDI QIDQ4881292

Jing Huang, Binay K. Bhattacharya, 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

algorithmcircular arcsmaximum weight cliqueproper circular arc graph\(q\)-coloring

Mathematics Subject Classification ID

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

Related Items (6)

A classification of locally semicomplete digraphs ⋮ A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs ⋮ Two remarks on circular arc graphs ⋮ Two cases of polynomial-time solvability for the coloring problem ⋮ Mutual exclusion scheduling with interval graphs or related classes. I ⋮ A surprising permanence of old motivations (a not-so-rigid story)

This page was built for publication: A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs