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

DOI10.1002/NET.3230030305zbMATH Open0259.05125DBLPjournals/networks/Gavril73OpenAlexW2052850644WikidataQ56210413 ScholiaQ56210413MaRDI QIDQ5675749FDOQ5675749

Cites Work

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

Cited In (63)

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

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

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