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
Autores principales: Joeris, B.L., Lin, M.C., McConnell, R.M., Spinrad, J.P., Szwarcfiter, J.L.
Formato: JOUR
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: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 todo:paper_01784617_v59_n2_p215_Joeris
record_format dspace
spelling todo:paper_01784617_v59_n2_p215_Joeris2023-10-03T15:08:18Z Linear-time recognition of Helly circular-arc models and graphs Joeris, B.L. Lin, M.C. McConnell, R.M. Spinrad, J.P. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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
Joeris, B.L.
Lin, M.C.
McConnell, R.M.
Spinrad, J.P.
Szwarcfiter, J.L.
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.
format JOUR
author Joeris, B.L.
Lin, M.C.
McConnell, R.M.
Spinrad, J.P.
Szwarcfiter, J.L.
author_facet Joeris, B.L.
Lin, M.C.
McConnell, R.M.
Spinrad, J.P.
Szwarcfiter, J.L.
author_sort Joeris, B.L.
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
url http://hdl.handle.net/20.500.12110/paper_01784617_v59_n2_p215_Joeris
work_keys_str_mv AT joerisbl lineartimerecognitionofhellycirculararcmodelsandgraphs
AT linmc lineartimerecognitionofhellycirculararcmodelsandgraphs
AT mcconnellrm lineartimerecognitionofhellycirculararcmodelsandgraphs
AT spinradjp lineartimerecognitionofhellycirculararcmodelsandgraphs
AT szwarcfiterjl lineartimerecognitionofhellycirculararcmodelsandgraphs
_version_ 1807322223371878400

Ejemplares similares