A Simpler Linear-Time Recognition of Circular-Arc Graphs

DOI10.1007/11785293_7MaRDI QIDQ5757898zbMATH OpenOpenAlexFDO

Authors Haim Kaplan, Yahav Nussbaum

Publication date 7 September 2007

Published in Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11785293_7

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Recommendations

• A simpler linear-time recognition of circular-arc graphs
• Linear-time recognition of circular-arc graphs
• scientific article; zbMATH DE number 437537
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Linear-time recognition of Helly circular-arc models and graphs
• Polynomial time recognition of unit circular-arc graphs
• Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs
• Recognizing circle graphs in polynomial time
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• scientific article; zbMATH DE number 5130726

Cited in

(22)

• Coloring fuzzy circular interval graphs
• Fully dynamic recognition of proper circular-arc graphs
• Recognition of Circle Graphs
• Proper Helly 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
• Some results on the limits of thought
• From a Circular-Arc Model to a Proper Circular-Arc Model
• Maximum max-k-clique subgraphs in cactus subtree graphs
• Essential obstacles to Helly circular-arc graphs
• scientific article; zbMATH DE number 437537 (Why is no real title available?)
• A simpler linear-time recognition of circular-arc graphs
• Recognizing generalized transmission graphs of line segments and circular sectors
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• 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
• Intersection representations of matrices by subtrees and unicycles on graphs
• A linear time algorithm to recognize circular permutation graphs
• Distributed interactive proofs for the recognition of some geometric intersection graph classes

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 Q5757898)