Characterizations and linear time recognition of helly circular-arc graphs

A circular-arc model (C, A) is a circle C together with a collection A of arcs of C. If A satisfies the Helly Property then (C, A) 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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Szwarcfiter, J.L.
Formato: SER
Materias:
Algorithms
Circular-arc graphs
Forbidden subgraphs
Helly circular-arc graphs
Computational complexity
Computational methods
Graphic methods
Mathematical models
Time series analysis
Helly circular-arc model
Recognition algorithms
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v4112LNCS_n_p73_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03029743_v4112LNCS_n_p73_Lin
record_format dspace
spelling todo:paper_03029743_v4112LNCS_n_p73_Lin2023-10-03T15:18:58Z Characterizations and linear time recognition of helly circular-arc graphs Lin, M.C. Szwarcfiter, J.L. Algorithms Circular-arc graphs Forbidden subgraphs Helly circular-arc graphs Algorithms Computational complexity Computational methods Graphic methods Mathematical models Time series analysis Circular-arc graphs Forbidden subgraphs Helly circular-arc model Recognition algorithms Graph theory A circular-arc model (C, A) is a circle C together with a collection A of arcs of C. If A satisfies the Helly Property then (C, A) 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 algorithm 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(n3). 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. © Springer-Verlag Berlin Heidelberg 2006. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v4112LNCS_n_p73_Lin
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
Algorithms
Computational complexity
Computational methods
Graphic methods
Mathematical models
Time series analysis
Circular-arc graphs
Forbidden subgraphs
Helly circular-arc model
Recognition algorithms
Graph theory
spellingShingle Algorithms
Circular-arc graphs
Forbidden subgraphs
Helly circular-arc graphs
Algorithms
Computational complexity
Computational methods
Graphic methods
Mathematical models
Time series analysis
Circular-arc graphs
Forbidden subgraphs
Helly circular-arc model
Recognition algorithms
Graph theory
Lin, M.C.
Szwarcfiter, J.L.
Characterizations and linear time recognition of helly circular-arc graphs
topic_facet Algorithms
Circular-arc graphs
Forbidden subgraphs
Helly circular-arc graphs
Algorithms
Computational complexity
Computational methods
Graphic methods
Mathematical models
Time series analysis
Circular-arc graphs
Forbidden subgraphs
Helly circular-arc model
Recognition algorithms
Graph theory
description A circular-arc model (C, A) is a circle C together with a collection A of arcs of C. If A satisfies the Helly Property then (C, A) 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 algorithm 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(n3). 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. © Springer-Verlag Berlin Heidelberg 2006.
format SER
author Lin, M.C.
Szwarcfiter, J.L.
author_facet Lin, M.C.
Szwarcfiter, J.L.
author_sort Lin, M.C.
title Characterizations and linear time recognition of helly circular-arc graphs
title_short Characterizations and linear time recognition of helly circular-arc graphs
title_full Characterizations and linear time recognition of helly circular-arc graphs
title_fullStr Characterizations and linear time recognition of helly circular-arc graphs
title_full_unstemmed Characterizations and linear time recognition of helly circular-arc graphs
title_sort characterizations and linear time recognition of helly circular-arc graphs
url http://hdl.handle.net/20.500.12110/paper_03029743_v4112LNCS_n_p73_Lin
work_keys_str_mv AT linmc characterizationsandlineartimerecognitionofhellycirculararcgraphs
AT szwarcfiterjl characterizationsandlineartimerecognitionofhellycirculararcgraphs
_version_ 1782023494566936576

Ejemplares similares