On cliques of Helly Circular-arc Graphs

A circular-arc graph is the intersection graph of a set of arcs on the circle. It is a Helly circular-arc graph if it has a Helly model, where every maximal clique is the set of arcs that traverse some clique point on the circle. A clique model is a Helly model that identifies one clique point for e...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Lin, Min Chih, Soulignac, Francisco Juan
Publicado:	2008
Materias:	algorithms clique graphs Helly circular-arc graphs maximum weight cliques proper Helly circular-arc graphs
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p117_Lin http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p117_Lin
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_15710653_v30_nC_p117_Lin
record_format	dspace
spelling	paper:paper_15710653_v30_nC_p117_Lin2023-06-08T16:24:23Z On cliques of Helly Circular-arc Graphs Lin, Min Chih Soulignac, Francisco Juan algorithms clique graphs Helly circular-arc graphs maximum weight cliques proper Helly circular-arc graphs A circular-arc graph is the intersection graph of a set of arcs on the circle. It is a Helly circular-arc graph if it has a Helly model, where every maximal clique is the set of arcs that traverse some clique point on the circle. A clique model is a Helly model that identifies one clique point for each maximal clique. A Helly circular-arc graph is proper if it has a Helly model where no arc is a subset of another. In this paper, we show that the clique intersection graphs of Helly circular-arc graphs are related to the proper Helly circular-arc graphs. This yields the first polynomial (linear) time recognition algorithm for the clique graphs of Helly circular-arc graphs. Next, we develop an O (n) time algorithm to obtain a clique model of Helly model, improving the previous O (n2) bound. This gives a linear-time algorithm to find a proper Helly model for the clique graph of a Helly circular-arc graph. As an application, we find a maximum weighted clique of a Helly circular-arc graph in linear time. © 2008 Elsevier B.V. All rights reserved. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2008 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p117_Lin http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p117_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 clique graphs Helly circular-arc graphs maximum weight cliques proper Helly circular-arc graphs
spellingShingle	algorithms clique graphs Helly circular-arc graphs maximum weight cliques proper Helly circular-arc graphs Lin, Min Chih Soulignac, Francisco Juan On cliques of Helly Circular-arc Graphs
topic_facet	algorithms clique graphs Helly circular-arc graphs maximum weight cliques proper Helly circular-arc graphs
description	A circular-arc graph is the intersection graph of a set of arcs on the circle. It is a Helly circular-arc graph if it has a Helly model, where every maximal clique is the set of arcs that traverse some clique point on the circle. A clique model is a Helly model that identifies one clique point for each maximal clique. A Helly circular-arc graph is proper if it has a Helly model where no arc is a subset of another. In this paper, we show that the clique intersection graphs of Helly circular-arc graphs are related to the proper Helly circular-arc graphs. This yields the first polynomial (linear) time recognition algorithm for the clique graphs of Helly circular-arc graphs. Next, we develop an O (n) time algorithm to obtain a clique model of Helly model, improving the previous O (n2) bound. This gives a linear-time algorithm to find a proper Helly model for the clique graph of a Helly circular-arc graph. As an application, we find a maximum weighted clique of a Helly circular-arc graph in linear time. © 2008 Elsevier B.V. All rights reserved.
author	Lin, Min Chih Soulignac, Francisco Juan
author_facet	Lin, Min Chih Soulignac, Francisco Juan
author_sort	Lin, Min Chih
title	On cliques of Helly Circular-arc Graphs
title_short	On cliques of Helly Circular-arc Graphs
title_full	On cliques of Helly Circular-arc Graphs
title_fullStr	On cliques of Helly Circular-arc Graphs
title_full_unstemmed	On cliques of Helly Circular-arc Graphs
title_sort	on cliques of helly circular-arc graphs
publishDate	2008
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15710653_v30_nC_p117_Lin http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p117_Lin
work_keys_str_mv	AT linminchih oncliquesofhellycirculararcgraphs AT soulignacfranciscojuan oncliquesofhellycirculararcgraphs
_version_	1768544749121175552

On cliques of Helly Circular-arc Graphs

Ejemplares similares