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

DOI10.1137/0214018zbMATH Open0567.68042OpenAlexW2025641440MaRDI QIDQ3683548FDOQ3683548

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

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

zbMATH Keywords

algorithms

Mathematics Subject Classification ID

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

Cited In (34)

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

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)