Finding maximum cliques in circle graphs

DOI10.1002/NET.3230110305MaRDI QIDQ3910008zbMATH OpenOpenAlexFDO

Authors Doron Rotem, J. Urrutia

Publication date 1981

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230110305

zbMATH Keywords

algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• Longest Increasing and Decreasing Subsequences
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(14)

• New clique and independent set algorithms for circle graphs
• The maximum clique problem
• Container ship stowage problem complexity and connection to the coloring of circle graphs
• Fast distance multiplication of unit-Monge matrices
• A maximum weight clique algorithm for dense circle graphs with many shared endpoints
• An algorithm for the maximum internally stable set in a weighted graph
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• A parallel algorithm to generate all maximal independent sets on permutation graphs
• A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
• Computing the all-pairs longest chains in the plane
• The complexity of colouring circle graphs (extended abstract)
• A branch and bound algorithm for the maximum clique problem
• New formulation for coloring circle graphs
• Finding maximum cliques in arbitrary and in special graphs

This page was built for publication: Finding maximum cliques in circle graphs

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