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, M.C., McConnell, R.M., Soulignac, F.J., Szwarcfiter, J.L.
Formato:	JOUR
Materias:	algorithms clique graphs Helly circular-arc graphs maximum weight cliques proper Helly circular-arc graphs
Acceso en línea:	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	todo:paper_15710653_v30_nC_p117_Lin
record_format	dspace
spelling	todo:paper_15710653_v30_nC_p117_Lin2023-10-03T16:27:01Z On cliques of Helly Circular-arc Graphs Lin, M.C. McConnell, R.M. Soulignac, F.J. Szwarcfiter, J.L. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, M.C. McConnell, R.M. Soulignac, F.J. Szwarcfiter, J.L. 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.
format	JOUR
author	Lin, M.C. McConnell, R.M. Soulignac, F.J. Szwarcfiter, J.L.
author_facet	Lin, M.C. McConnell, R.M. Soulignac, F.J. Szwarcfiter, J.L.
author_sort	Lin, M.C.
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
url	http://hdl.handle.net/20.500.12110/paper_15710653_v30_nC_p117_Lin
work_keys_str_mv	AT linmc oncliquesofhellycirculararcgraphs AT mcconnellrm oncliquesofhellycirculararcgraphs AT soulignacfj oncliquesofhellycirculararcgraphs AT szwarcfiterjl oncliquesofhellycirculararcgraphs
_version_	1807316161676705792

On cliques of Helly Circular-arc Graphs

Ejemplares similares