Characterizations and recognition of circular-arc graphs and subclasses: A survey

Mostrar todas las versiones(3)

Circular graphs are intersection graphs of arcs on a circle. These graphs are reported to have been studied since 1964, and they have been receiving considerable attention since a series of papers by Tucker in the 1970s. Various subclasses of circular-arc graphs have also been studied. Among these a...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Lin, M.C., Szwarcfiter, J.L.
Formato:	JOUR
Materias:	Algorithms Circular-arc graphs Co-bipartite circular-arc graphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Surveys Cavity resonators
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_0012365X_v309_n18_p5618_Lin
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_0012365X_v309_n18_p5618_Lin
record_format	dspace
spelling	todo:paper_0012365X_v309_n18_p5618_Lin2023-10-03T14:10:21Z Characterizations and recognition of circular-arc graphs and subclasses: A survey Lin, M.C. Szwarcfiter, J.L. Algorithms Circular-arc graphs Co-bipartite circular-arc graphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Circular-arc graphs Co-bipartite circular-arc graphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Algorithms Surveys Cavity resonators Circular graphs are intersection graphs of arcs on a circle. These graphs are reported to have been studied since 1964, and they have been receiving considerable attention since a series of papers by Tucker in the 1970s. Various subclasses of circular-arc graphs have also been studied. Among these are the proper circular-arc graphs, unit circular-arc graphs, Helly circular-arc graphs and co-bipartite circular-arc graphs. Several characterizations and recognition algorithms have been formulated for circular-arc graphs and its subclasses. In particular, it should be mentioned that linear time algorithms are known for all these classes of graphs. In the present paper, we survey these characterizations and recognition algorithms, with emphasis on the linear time algorithms. © 2008 Elsevier B.V. All rights reserved. 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_0012365X_v309_n18_p5618_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 Co-bipartite circular-arc graphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Circular-arc graphs Co-bipartite circular-arc graphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Algorithms Surveys Cavity resonators
spellingShingle	Algorithms Circular-arc graphs Co-bipartite circular-arc graphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Circular-arc graphs Co-bipartite circular-arc graphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Algorithms Surveys Cavity resonators Lin, M.C. Szwarcfiter, J.L. Characterizations and recognition of circular-arc graphs and subclasses: A survey
topic_facet	Algorithms Circular-arc graphs Co-bipartite circular-arc graphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Circular-arc graphs Co-bipartite circular-arc graphs Helly circular-arc graphs Proper circular-arc graphs Unit circular-arc graphs Algorithms Surveys Cavity resonators
description	Circular graphs are intersection graphs of arcs on a circle. These graphs are reported to have been studied since 1964, and they have been receiving considerable attention since a series of papers by Tucker in the 1970s. Various subclasses of circular-arc graphs have also been studied. Among these are the proper circular-arc graphs, unit circular-arc graphs, Helly circular-arc graphs and co-bipartite circular-arc graphs. Several characterizations and recognition algorithms have been formulated for circular-arc graphs and its subclasses. In particular, it should be mentioned that linear time algorithms are known for all these classes of graphs. In the present paper, we survey these characterizations and recognition algorithms, with emphasis on the linear time algorithms. © 2008 Elsevier B.V. All rights reserved.
format	JOUR
author	Lin, M.C. Szwarcfiter, J.L.
author_facet	Lin, M.C. Szwarcfiter, J.L.
author_sort	Lin, M.C.
title	Characterizations and recognition of circular-arc graphs and subclasses: A survey
title_short	Characterizations and recognition of circular-arc graphs and subclasses: A survey
title_full	Characterizations and recognition of circular-arc graphs and subclasses: A survey
title_fullStr	Characterizations and recognition of circular-arc graphs and subclasses: A survey
title_full_unstemmed	Characterizations and recognition of circular-arc graphs and subclasses: A survey
title_sort	characterizations and recognition of circular-arc graphs and subclasses: a survey
url	http://hdl.handle.net/20.500.12110/paper_0012365X_v309_n18_p5618_Lin
work_keys_str_mv	AT linmc characterizationsandrecognitionofcirculararcgraphsandsubclassesasurvey AT szwarcfiterjl characterizationsandrecognitionofcirculararcgraphsandsubclassesasurvey
_version_	1807323694513520640

Characterizations and recognition of circular-arc graphs and subclasses: A survey

Ejemplares similares