A simpler linear-time recognition of circular-arc graphs
DOI10.1007/S00453-010-9432-YzbMATH Open1234.68326DBLPjournals/algorithmica/KaplanN11aOpenAlexW2160399627WikidataQ60307429 ScholiaQ60307429MaRDI QIDQ644807FDOQ644807
Authors: Haim Kaplan, Yahav Nussbaum 
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
Recommendations
intersection graphcircular-arc graphrecognition algorithmcircular-arc modelconsecutive-ones property
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Modular decomposition and transitive orientation
- Efficient graph representations
- Linear-time recognition of circular-arc graphs
- Algorithms on circular-arc graphs
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Title not available (Why is that?)
- PC trees and circular-ones arrangements.
- Matrix characterizations of circular-arc graphs
- Circular-arc graphs with clique cover number two
- Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
- A Simpler Linear-Time Recognition of Circular-Arc Graphs
- Title not available (Why is that?)
- An Efficient Test for Circular-Arc Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (15)
- Recognition of Circle Graphs
- Fully dynamic recognition of proper circular-arc graphs
- A Simpler Linear-Time Recognition of Circular-Arc Graphs
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- On the recognition of digital circles in linear time
- Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
- Linear-time recognition of circular-arc graphs
- Reconfiguring shortest paths in graphs
- Title not available (Why is that?)
- Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
- Recognizing generalized transmission graphs of line segments and circular sectors
- Induced disjoint paths in circular-arc graphs in linear time
- Polynomial time recognition of unit circular-arc graphs
- A linear time algorithm to recognize circular permutation graphs
- Normal Helly circular-arc graphs and its subclasses
This page was built for publication: A simpler 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 Q644807)
