A simpler linear-time recognition of circular-arc graphs
From MaRDI portal
Publication:644807
DOI10.1007/s00453-010-9432-yzbMath1234.68326WikidataQ60307429 ScholiaQ60307429MaRDI QIDQ644807
Publication date: 7 November 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-010-9432-y
intersection graph; recognition algorithm; circular-arc graph; circular-arc model; consecutive-ones property
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection, Normal Helly circular-arc graphs and its subclasses, Induced disjoint paths in circular-arc graphs in linear time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Circular-arc graphs with clique cover number two
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Modular decomposition and transitive orientation
- Efficient graph representations
- PC trees and circular-ones arrangements.
- Linear-time recognition of circular-arc graphs
- Matrix characterizations of circular-arc graphs
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- An Efficient Test for Circular-Arc Graphs
- Algorithms on circular-arc graphs
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- A Simpler Linear-Time Recognition of Circular-Arc Graphs
