Algorithms for a maximum clique and a maximum independent set of a circle graph

DOI10.1002/net.3230030305zbMath0259.05125WikidataQ56210413 ScholiaQ56210413MaRDI QIDQ5675749

Fanica Gavril

Publication date: 1973

Published in: Networks (Search for Journal in Brave)

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

Mathematics Subject Classification ID

05C99: Graph theory

05-04: Software, source code, etc. for problems pertaining to combinatorics

Related Items

Using Fifth Generation Tools for Solving the Clique Number Problem, Trapezoid graphs and generalizations, geometry and algorithms, Independence and domination in polygon graphs, Representations of graphs and networks (coding, layouts and embeddings), New clique and independent set algorithms for circle graphs, Finding a maximum set of independent chords in a circle, Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs, On a graph partition problem with application to VLSI layout, The complexity of domination problems in circle graphs, Some simplified NP-complete graph problems, The maximum clique problem, An exact algorithm for the maximum stable set problem, Maximum independent set and maximum clique algorithms for overlap graphs, Container ship stowage problem complexity and connection to the coloring of circle graphs, On the computational complexity of 2-interval pattern matching problems

Cites Work

• On rigid circuit graphs
• Incidence matrices and interval graphs
• A Characterization of Comparability Graphs and of Interval Graphs