Linear-Time Recognition of Helly Circular-Arc Models and Graphs

Benson Joeris, Min Chih Lin, Ross M. McConnell, Jeremy Spinrad, Jayme L. Szwarcfiter

Type: Article

Publication Date: 2009-04-07

Citations: 26

DOI: https://doi.org/10.1007/s00453-009-9304-5

View Publication

Download PDF

Locations

CiteSeer X (The Pennsylvania State University) - View - PDF
Algorithmica - View

Similar Works

Action	Title	Year	Authors
+	Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs	2006	Min Chih Lin Jayme L. Szwarcfiter
+	Forbidden Induced Subgraphs of Normal Helly Circular-Arc Graphs: Characterization and Detection	2014	Yixin Cao Luciano N. Grippo Martín D. Safe
+	Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm	2014	Mathew C. Francis Pavol Hell Juraj Stacho
+	Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm	2014	Mathew C. Francis Pavol Hell Juraj Stacho
+ PDF Chat	Circular-arc graphs and the Helly property	2024	Jan Derbisz Tomasz Krawczyk
+	Subclasses of Circular-Arc Bigraphs: Helly, Normal and Proper	2019	Marina Groshaus André Guedes Fabricio Schiavon Kolberg
+	An Efficient Test for Circular-Arc Graphs	1980	Alan Tucker
+	Forbidden induced subgraphs of normal Helly circular-arc graphs: Characterization and detection	2015	Yixin Cao Luciano N. Grippo Martín D. Safe
+ PDF Chat	A certifying and dynamic algorithm for the recognition of proper circular-arc graphs	2021	Francisco J. Soulignac
+	A certifying and dynamic algorithm for the recognition of proper circular-arc graphs	2015	Francisco J. Soulignac
+	A certifying and dynamic algorithm for the recognition of proper circular-arc graphs	2015	Francisco J. Soulignac
+	Extending Partial Representations of Circular-Arc Graphs	2021	Jiřı́ Fiala Ignaz Rutter Péter Stumpf Peter Zeman
+	The clique operator on circular-arc graphs	2009	Min Chih Lin Francisco J. Soulignac Jayme L. Szwarcfiter
+	Recognition of Perfect Circular-arc Graphs	2006	Kathie Cameron Elaine M. Eschen Chı́nh T. Hoàng R. Sritharan
+ PDF Chat	Comments on "$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs"	2024	Tomasz Krawczyk
+	Extending Partial Representations of Unit Circular-arc Graphs.	2017	Jiřı́ Fiala Ignaz Rutter Peter Stumpf Peter Zeman
+	On circular-arc graphs having a model with no three arcs covering the circle	2014	Luciano N. Grippo Martín D. Safe
+	Essential obstacles to Helly circular-arc graphs	2016	Martín D. Safe
+ PDF Chat	Characterization of Chordal Circular-arc Graphs: I. Split Graphs	2024	Yixin Cao Jan Derbisz Tomasz Krawczyk
+	From a Circular-Arc Model to a Proper Circular-Arc Model	2008	Yahav Nussbaum

Works That Cite This (19)

Action	Title	Year	Authors
+	On neighborhood-Helly graphs	2016	Marina Groshaus Min Chih Lin Jayme L. Szwarcfiter
+ PDF Chat	Balancedness of some subclasses of circular-arc graphs	2010	Flavia Bonomo Guillermo Durán Martín D. Safe Annegret K. Wagler
+	Structural results on circular-arc graphs and circle graphs: A survey and the main open problems	2013	Guillermo Durán Luciano N. Grippo Martín D. Safe
+ PDF Chat	Isomorphism of graph classes related to the circular-ones property	2013	Andrew R. Curtis Min Chih Lin Ross M. McConnell Yahav Nussbaum Francisco J. Soulignac Jeremy Spinrad Jayme L. Szwarcfiter
+ PDF Chat	Balancedness of subclasses of circular-arc graphs	2014	Flavia Bonomo Guillermo Durán Martín D. Safe Annegret K. Wagler
+ PDF Chat	Characterization and linear‐time detection of minimal obstructions to concave‐round graphs and the circular‐ones property	2019	Martín D. Safe
+ PDF Chat	Canonical Representations for Circular-Arc Graphs Using Flip Sets	2018	Maurice Chandoo
+	Complexity Aspects of the Helly Property: Graphs and Hypergraphs	2009	Mitre C. Dourado Fábio Protti Jayme L. Szwarcfiter
+	Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space	2012	Johannes Köbler Sebastian Kuhnert Oleg Verbitsky
+	Graph Classes with Structured Neighborhoods and Algorithmic Applications	2011	Rémy Belmonte Martin Vatshelle

Works Cited by This (5)

Action	Title	Year	Authors
+	Characterizations and Linear Time Recognition of Helly Circular-Arc Graphs	2006	Min Chih Lin Jayme L. Szwarcfiter
+	An Efficient Test for Circular-Arc Graphs	1980	Alan Tucker
+ PDF Chat	A Simpler Linear-Time Recognition of Circular-Arc Graphs	2006	Haim Kaplan Yahav Nussbaum
+	Unit Circular-Arc Graph Representations and Feasible Circulations	2008	Min Chih Lin Jayme L. Szwarcfiter
+	Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing	2000	Michel Habib Ross M. McConnell Christophe Paul Laurent Viennot