A simpler linear-time recognition of circular-arc graphs

DOI10.1007/S00453-010-9432-YMaRDI QIDQ644807zbMATH OpenOpenAlexDBLPWikidataFDO

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

zbMATH Keywords

intersection graphcircular-arc graphrecognition algorithmcircular-arc modelconsecutive-ones property

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Linear-time recognition of circular-arc graphs
• scientific article; zbMATH DE number 437537
• Linear time algorithms on circular-arc graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey

Cites work

• scientific article; zbMATH DE number 437537 (Why is no real title available?)
• scientific article; zbMATH DE number 3825206 (Why is no real title available?)
• scientific article; zbMATH DE number 2119749 (Why is no real title available?)
• scientific article; zbMATH DE number 2123255 (Why is no real title available?)
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Algorithms on circular-arc graphs
• An Efficient Test for Circular-Arc Graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Circular-arc graphs with clique cover number two
• Efficient graph representations
• Linear-time recognition of circular-arc graphs
• Matrix characterizations of circular-arc graphs
• Modular decomposition and transitive orientation
• PC trees and circular-ones arrangements.
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(15)

• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Reconfiguring shortest paths in graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
• Recognition of Circle Graphs
• Fully dynamic recognition of proper circular-arc graphs
• Polynomial time recognition of unit circular-arc graphs
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Linear-time recognition of circular-arc graphs
• scientific article; zbMATH DE number 437537 (Why is no real title available?)
• Recognizing generalized transmission graphs of line segments and circular sectors
• Normal Helly circular-arc graphs and its subclasses
• Induced disjoint paths in circular-arc graphs in linear time
• On the recognition of digital circles in linear time
• A linear time algorithm to recognize circular permutation graphs

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)