An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs

DOI10.1016/0020-0190(89)90220-2zbMath0677.68056OpenAlexW1978033460MaRDI QIDQ1123622

S. H. Smith

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90220-2

zbMATH Keywords

bipartite graphsmaximum weight clique problemmaximum weight clique algorithmmaximum weight independent sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Related Items (9)

Maximum weight independent set of circular-arc graph and its application ⋮ On cliques of Helly Circular-arc Graphs ⋮ Distributed algorithms for maximum cliques ⋮ Two remarks on circular arc graphs ⋮ Parallel algorithms on circular-arc graphs ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Algorithms for clique-independent sets on subclasses of circular-arc graphs ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications ⋮ Perfect circular arc coloring

Cites Work

• Unnamed Item
• Unnamed Item
• Interval graphs and related topics
• Finding maximum cliques on circular-arc graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Preserving order in a forest in less than logarithmic time and linear space
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Stability in circular arc graphs
• An Efficient Test for Circular-Arc Graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Algorithms on circular-arc graphs
• Coloring a Family of Circular Arcs

This page was built for publication: An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs