An Efficient Test for Circular-Arc Graphs
From MaRDI portal
Publication:3900112
Cited in
(49)- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Reconfiguring shortest paths in graphs
- Extending partial representations of circular-arc graphs
- Precoloring extension. I: Interval graphs
- On a circle-cover minimization problem
- Periodic assignment and graph colouring
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- Maximum bipartite subgraphs of geometric intersection graphs
- On polygon numbers of circle graphs and distance hereditary graphs
- Optimal circular arc representations: Properties, recognition, and construction
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- Finding Hamiltonian circuits in proper interval graphs
- A model predictive control approach for discrete-time rescheduling in complex central railway station areas
- Deferred-query—An efficient approach for problems on interval and circular-arc graphs
- An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
- A constant factor approximation algorithm for boxicity of circular arc graphs
- A simpler linear-time recognition of circular-arc graphs
- Efficient parallel recognition of some circular arc graphs. I
- Algorithms for clique-independent sets on subclasses of circular-arc graphs
- Parallel algorithms on circular-arc graphs
- Completing colored graphs to meet a target property
- Algorithmic aspects of intersection graphs and representation hypergraphs
- Contact representations of planar graphs: extending a partial representation is hard
- Graphs and digraphs represented by intervals and circular arcs
- On the structure of certain intersection graphs
- An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- Two remarks on circular arc graphs
- Lexicographic orientation algorithms
- Efficient reduction for path problems on circular-arc graphs
- New characterizations of proper interval bigraphs
- Linear-time recognition of Helly circular-arc models and graphs
- Intersection graphs of concatenable subtrees of graphs
- The complexity of colouring circle graphs (extended abstract)
- An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
- A short proof of the NP-completeness of minimum sum interval coloring
- From a Circular-Arc Model to a Proper Circular-Arc Model
- A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
- Minimum entropy combinatorial optimization problems
- Tree loop graphs
- Dominating sets and domatic number of circular arc graphs
- Interval routing schemes for circular-arc graphs
- Circular-arc graphs with clique cover number two
- Representations of graphs and networks (coding, layouts and embeddings)
- Optimal parallel algorithms on circular-arc graphs
- An O(qn) algorithm to q-color a proper family of circular arcs
- Minimum entropy coloring
- On powers of circular arc graphs and proper circular arc graphs
- The Complexity of Coloring Circular Arcs and Chords
This page was built for publication: An Efficient Test for Circular-Arc Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3900112)
