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

DOI10.1016/0020-0190(89)90220-2MaRDI QIDQ1123622zbMATH OpenOpenAlexFDO

Authors 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 algorithmmaximum weight clique problemmaximum weight independent sets

Mathematics Subject Classification ID

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

Recommendations

• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
• scientific article; zbMATH DE number 3891419
• Finding maximum cliques on circular-arc graphs
• Finding a Maximum Clique in a Set of Proper Circular Arcs in Time O(n) with Applications

Cites work

• Algorithms on circular-arc graphs
• An Efficient Test for Circular-Arc Graphs
• An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• Coloring a Family of Circular Arcs
• Efficient algorithms for interval graphs and circular-arc graphs
• Finding maximum cliques on circular-arc graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• Interval graphs and related topics
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• Preserving order in a forest in less than logarithmic time and linear space
• Stability in circular arc graphs

Cited in

(20)

• On a circle placement problem
• Efficient parallel recognition of some circular arc graphs. I
• Finding a maximum matching in a circular-arc graph
• \(k\) best cuts for circular-arc graphs
• Maximum independent set and maximum clique algorithms for overlap graphs
• Avoidable vertices and edges in graphs: existence, characterization, and applications
• Algorithms for clique-independent sets on subclasses of circular-arc graphs
• Perfect circular arc coloring
• scientific article; zbMATH DE number 3891419 (Why is no real title available?)
• On cliques of Helly Circular-arc Graphs
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph
• Distributed algorithms for maximum cliques
• 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
• scientific article; zbMATH DE number 1555975 (Why is no real title available?)
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
• Parallel algorithms on circular-arc graphs
• Two remarks on circular arc graphs
• Maximum weight independent set of circular-arc graph and its application

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

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