From a Circular-Arc Model to a Proper Circular-Arc Model
From MaRDI portal
Publication:5302066
DOI10.1007/978-3-540-92248-3_29zbMath1202.05139MaRDI QIDQ5302066
Publication date: 20 January 2009
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_29
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
Normal Helly circular-arc graphs and its subclasses, Essential obstacles to Helly circular-arc graphs
Cites Work
- Unnamed Item
- Linear-time recognition of Helly circular-arc models and graphs
- Linear time algorithms on circular-arc graphs
- Efficient graph representations
- Linear-time recognition of circular-arc graphs
- An \(0(n^{1.5})\) algorithm to color proper circular arcs
- Algorithmic graph theory and perfect graphs
- Structure theorems for some circular-arc graphs
- Proper Helly Circular-Arc Graphs
- Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
- Efficient construction of unit circular-arc models
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- Stability in circular arc graphs
- An Efficient Test for Circular-Arc Graphs
- A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- A Simpler Linear-Time Recognition of Circular-Arc Graphs
