Linear-time recognition of Helly circular-arc models and graphs

A circular-arc model M is a circle C together with a collection A of arcs of C. If A satisfies the Helly Property then · is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the objec...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Lin, Min Chih
Publicado:	2011
Materias:	Algorithms Circular-arc graphs Forbidden subgraphs Helly circular-arc graphs Arc models Circular-arc graph Forbidden induced subgraphs General class Intersection graph Recognition algorithm Characterization Graphic methods
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v59_n2_p215_Joeris http://hdl.handle.net/20.500.12110/paper_01784617_v59_n2_p215_Joeris
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_01784617_v59_n2_p215_Joeris
record_format	dspace
spelling	paper:paper_01784617_v59_n2_p215_Joeris2023-06-08T15:19:17Z Linear-time recognition of Helly circular-arc models and graphs Lin, Min Chih Algorithms Circular-arc graphs Forbidden subgraphs Helly circular-arc graphs Arc models Circular-arc graph Forbidden induced subgraphs Forbidden subgraphs General class Intersection graph Recognition algorithm Algorithms Characterization Graphic methods A circular-arc model M is a circle C together with a collection A of arcs of C. If A satisfies the Helly Property then · is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n 3). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound. © 2009 Springer Science+Business Media, LLC. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2011 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v59_n2_p215_Joeris http://hdl.handle.net/20.500.12110/paper_01784617_v59_n2_p215_Joeris
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Algorithms Circular-arc graphs Forbidden subgraphs Helly circular-arc graphs Arc models Circular-arc graph Forbidden induced subgraphs Forbidden subgraphs General class Intersection graph Recognition algorithm Algorithms Characterization Graphic methods
spellingShingle	Algorithms Circular-arc graphs Forbidden subgraphs Helly circular-arc graphs Arc models Circular-arc graph Forbidden induced subgraphs Forbidden subgraphs General class Intersection graph Recognition algorithm Algorithms Characterization Graphic methods Lin, Min Chih Linear-time recognition of Helly circular-arc models and graphs
topic_facet	Algorithms Circular-arc graphs Forbidden subgraphs Helly circular-arc graphs Arc models Circular-arc graph Forbidden induced subgraphs Forbidden subgraphs General class Intersection graph Recognition algorithm Algorithms Characterization Graphic methods
description	A circular-arc model M is a circle C together with a collection A of arcs of C. If A satisfies the Helly Property then · is a Helly circular-arc model. A (Helly) circular-arc graph is the intersection graph of a (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly circular-arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n 3). In this article, we describe different characterizations for Helly circular-arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound. © 2009 Springer Science+Business Media, LLC.
author	Lin, Min Chih
author_facet	Lin, Min Chih
author_sort	Lin, Min Chih
title	Linear-time recognition of Helly circular-arc models and graphs
title_short	Linear-time recognition of Helly circular-arc models and graphs
title_full	Linear-time recognition of Helly circular-arc models and graphs
title_fullStr	Linear-time recognition of Helly circular-arc models and graphs
title_full_unstemmed	Linear-time recognition of Helly circular-arc models and graphs
title_sort	linear-time recognition of helly circular-arc models and graphs
publishDate	2011
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v59_n2_p215_Joeris http://hdl.handle.net/20.500.12110/paper_01784617_v59_n2_p215_Joeris
work_keys_str_mv	AT linminchih lineartimerecognitionofhellycirculararcmodelsandgraphs
_version_	1768542549478211584

Linear-time recognition of Helly circular-arc models and graphs

Ejemplares similares