Linear-time recognition of circular-arc graphs
From MaRDI portal
Recommendations
- A simpler linear-time recognition of circular-arc graphs
- A Simpler Linear-Time Recognition of Circular-Arc Graphs
- scientific article; zbMATH DE number 437537
- Polynomial time recognition of unit circular-arc graphs
- Linear-time recognition of Helly circular-arc models and graphs
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- Recognizing circle graphs in polynomial time
- Linear time algorithms on circular-arc graphs
- Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
- A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
Cited in
(88)- Integral mixed unit interval graphs
- Normal Helly circular-arc graphs and its subclasses
- Canonical representations for circular-arc graphs using flip sets
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Graph classes with structured neighborhoods and algorithmic applications
- Algorithms for clique-independent sets on subclasses of circular-arc graphs
- Pathwidth of Circular-Arc Graphs
- Loop Graphs and Asteroidal Sets
- On the recognition of fuzzy circular interval graphs
- On the isomorphism problem for Helly circular-arc graphs
- Disconnected cuts in claw-free graphs
- Disconnected cuts in claw-free graphs
- Powers of cycles, powers of paths, and distance graphs
- Solving the path cover problem on circular-arc graphs by using an approximation algorithm
- Coloring fuzzy circular interval graphs
- Colouring Some Classes of Perfect Graphs Robustly
- Interval graph representation with given interval and intersection lengths
- Graphs and digraphs represented by intervals and circular arcs
- Recognizing edge clique graphs among interval graphs and probe interval graphs
- Lexicographic orientation algorithms
- Co-TT graphs and a characterization of split co-TT graphs
- Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
- Linear-time recognition of Helly circular-arc models and graphs
- Recognizing threshold tolerance graphs in \(O(n^2)\) time
- Fully dynamic recognition of proper circular-arc graphs
- Recognition of Circle Graphs
- A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs
- NP-completeness results for edge modification problems
- List matrix partitions of graphs representing geometric configurations
- Obstacle numbers of graphs
- SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS
- A Simpler Linear-Time Recognition of Circular-Arc Graphs
- On the structure of certain intersection graphs
- Proper Helly Circular-Arc Graphs
- Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- Circular-arc bigraphs and its subclasses
- On the recognition of digital circles in linear time
- FO model checking on geometric graphs
- On orthogonal ray graphs
- Subclasses of circular-arc bigraphs: Helly, normal and proper
- Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
- An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
- Min-orderable digraphs
- Interval routing schemes for circular-arc graphs
- FO model checking of geometric graphs
- On the hyperbolicity constant of circular-arc graphs
- Graph classes with structured neighborhoods and algorithmic applications
- From a Circular-Arc Model to a Proper Circular-Arc Model
- Maximum max-k-clique subgraphs in cactus subtree graphs
- Characterising \((k,\ell )\)-leaf powers
- Bipartite Analogues of Comparability and Cocomparability Graphs
- Computing optimal leaf roots of chordal cographs in linear time
- Efficient and perfect domination on circular-arc graphs
- Essential obstacles to Helly circular-arc graphs
- 2-nested matrices: towards understanding the structure of circle graphs
- A linear-time algorithm for paired-domination on circular-arc graphs
- Interval-like graphs and digraphs
- Succinct encodings for families of interval graphs
- Partial Characterizations of Circular-Arc Graphs
- Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
- Max point-tolerance graphs
- On recognition of threshold tolerance graphs and their complements
- scientific article; zbMATH DE number 437537 (Why is no real title available?)
- scientific article; zbMATH DE number 6829367 (Why is no real title available?)
- Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
- Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
- Reconstructing a graph from its arc incidence graph
- A simpler linear-time recognition of circular-arc graphs
- A graph-theoretic barcode ordering model for linked-reads
- The complexity of the list homomorphism problem for graphs
- Avoidable vertices and edges in graphs: existence, characterization, and applications
- Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number
- Recognizing generalized transmission graphs of line segments and circular sectors
- Partial characterizations of circular-arc graphs
- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
- Induced disjoint paths in circular-arc graphs in linear time
- The clique operator on circular-arc graphs
- Characterizations and recognition of circular-arc graphs and subclasses: a survey
- Polynomial time recognition of unit circular-arc graphs
- On partitioning interval graphs into proper interval subgraphs and related problems
- Characterising circular-arc contact \(B_0\)-VPG graphs
- Extending partial representations of circular-arc graphs
- A constant factor approximation algorithm for boxicity of circular arc graphs
- Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs
- A linear time algorithm to recognize circular permutation graphs
- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- A polynomial kernel for proper Helly circular-arc vertex deletion
This page was built for publication: Linear-time recognition of circular-arc graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1424251)
