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

DOI10.1002/NET.3230030305zbMath0259.05125DBLPjournals/networks/Gavril73OpenAlexW2052850644WikidataQ56210413 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

Graph theory (05C99) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (63)

An exact algorithm for the maximum stable set problem ⋮ The Complexity of Coloring Circular Arcs and Chords ⋮ Improved bounds for colouring circle graphs ⋮ Models and Algorithms for Genome Rearrangement with Positional Constraints ⋮ On the computational complexity of 2-interval pattern matching problems ⋮ Maximum weight independent sets and cliques in intersection graphs of filaments ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ On some applications of the selective graph coloring problem ⋮ Computing the all-pairs longest chains in the plane ⋮ On decomposing polygons into uniformly monotone parts ⋮ Tree search for the stacking problem ⋮ On dimensional properties of graphs ⋮ An algorithm for finding a maximum weighted independent set in an arbitrary graph ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ A Faster Algorithm for Maximum Induced Matchings on Circle Graphs ⋮ The complexity of colouring circle graphs ⋮ Online Bounded Coloring of Permutation and Overlap Graphs ⋮ On streaming algorithms for geometric independent set and clique ⋮ On the online track assignment problem ⋮ Counting hexagonal patches and independent sets in circle graphs ⋮ Algorithms for induced biclique optimization problems ⋮ Maximum independent set and maximum clique algorithms for overlap graphs ⋮ Independent sets and chromatic numbers of circle graphs ⋮ Parameterized domination in circle graphs ⋮ A Maximum Weight Clique Algorithm For Dense Circle Graphs With Many Shared Endpoints ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ 3D-interval-filament graphs ⋮ New clique and independent set algorithms for circle graphs ⋮ Finding a maximum set of independent chords in a circle ⋮ Trapezoid graphs and generalizations, geometry and algorithms ⋮ Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs ⋮ Independence and domination in polygon graphs ⋮ On a graph partition problem with application to VLSI layout ⋮ A branch and bound algorithm for the maximum clique problem ⋮ Minimum weight feedback vertex sets in circle graphs ⋮ The complexity of domination problems in circle graphs ⋮ Trapezoid graphs and generalizations, geometry and algorithms ⋮ Some simplified NP-complete graph problems ⋮ Unnamed Item ⋮ Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs ⋮ A \((1.5+\varepsilon)\)-approximation algorithm for weighted connectivity augmentation ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs ⋮ Generalised online colouring problems in overlap graphs ⋮ Layered graphs: applications and algorithms ⋮ Leaf sector covers with applications on circle graphs ⋮ Reconfiguring shortest paths in graphs ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ Unnamed Item ⋮ Using Fifth Generation Tools for Solving the Clique Number Problem ⋮ An output sensitive algorithm for computing a maximum independent set of a circle graph ⋮ Container ship stowage problem complexity and connection to the coloring of circle graphs ⋮ On the chromatic number of disjointness graphs of curves ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture ⋮ APX-hardness of domination problems in circle graphs ⋮ Finding Hamiltonian circuits in proper interval graphs ⋮ On the chromatic number of multiple interval graphs and overlap graphs ⋮ Finding maximum cliques in arbitrary and in special graphs ⋮ The maximum clique problem ⋮ The maximum clique problem in multiple interval graphs ⋮ Fast distance multiplication of unit-Monge matrices ⋮ An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs

Cites Work

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

This page was built for publication: Algorithms for a maximum clique and a maximum independent set of a circle graph