Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs

DOI10.1137/0214018MaRDI QIDQ3683548zbMATH OpenOpenAlexFDO

Authors

Publication date 1985

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0214018

zbMATH Keywords

algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• 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 Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs

Cited in

(38)

• Hadwiger's conjecture for proper circular arc graphs
• On a circle placement problem
• Finding maximum cliques on circular-arc graphs
• Algorithmic aspects of intersection graphs and representation hypergraphs
• An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
• Representations of graphs and networks (coding, layouts and embeddings)
• New clique and independent set algorithms for circle graphs
• Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
• Efficient parallel recognition of some circular arc graphs. I
• Optimal parallel algorithms on circular-arc graphs
• Parallel algorithms for permutation graphs
• The maximum clique problem
• Combinatorial problems on \(H\)-graphs
• List matrix partitions of graphs representing geometric configurations
• On powers of circular arc graphs and proper circular arc graphs
• Finding cliques of maximum weight on a generalization of permutation graphs
• On strict (outer-)confluent graphs
• Maximum clique exhaustive search in circulant \(k\)-hypergraphs
• The maximum clique problem in multiple interval graphs
• Fast distance multiplication of unit-Monge matrices
• A maximum weight clique algorithm for dense circle graphs with many shared endpoints
• OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS
• scientific article; zbMATH DE number 3891419 (Why is no real title available?)
• AnO(m+nlogn) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs
• A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
• Computing the all-pairs longest chains in the plane
• On strict (outer-)confluent graphs
• Parallel algorithms on circular-arc graphs
• A branch and bound algorithm for the maximum clique problem
• On \(H\)-topological intersection graphs
• Extending partial representations of circular-arc graphs
• Two remarks on circular arc graphs
• The minimum clique routing problem on cycles
• Sublinear hitting sets for some geometric graphs
• Efficient reduction for path problems on circular-arc graphs
• Maximum weight independent set of circular-arc graph and its application
• A parallel algorithm for finding a maximum clique of a set of circular arcs of a circle

This page was built for publication: Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs

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