The clique operator on circular-arc graphs

Mostrar todas las versiones(3)

A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is Helly when the arcs satisfy the Helly Property, while the model is proper Helly w...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Soulignac, F.J., Szwarcfiter, J.L.
Formato: JOUR
Materias:
Algorithms
Clique graphs
Helly circular-arc graphs
K-behavior
Proper Helly circular-arc graphs
Circular-arc graph
Complete solutions
Graph G
Intersection graph
Linear time
Recognition algorithm
Graph theory
Mathematical operators
Graphic methods
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n12_p1259_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_0166218X_v158_n12_p1259_Lin
record_format dspace
spelling todo:paper_0166218X_v158_n12_p1259_Lin2023-10-03T15:03:37Z The clique operator on circular-arc graphs Lin, M.C. Soulignac, F.J. Szwarcfiter, J.L. Algorithms Clique graphs Helly circular-arc graphs K-behavior Proper Helly circular-arc graphs Circular-arc graph Clique graphs Complete solutions Graph G Intersection graph K-behavior Linear time Recognition algorithm Algorithms Graph theory Mathematical operators Graphic methods A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is Helly when the arcs satisfy the Helly Property, while the model is proper Helly when it is simultaneously proper and Helly. A graph admitting a Helly (resp. proper Helly) model is called a Helly (resp. proper Helly) circular-arc graph. The clique graphK (G) of a graph G is the intersection graph of its cliques. The iterated clique graphKi (G) of G is defined by K0 (G) = G and Ki + 1 (G) = K (Ki (G)). In this paper, we consider two problems on clique graphs of circular-arc graphs. The first is to characterize clique graphs of Helly circular-arc graphs and proper Helly circular-arc graphs. The second is to characterize the graph to which a general circular-arc graph K-converges, if it is K-convergent. We propose complete solutions to both problems, extending the partial results known so far. The methods lead to linear time recognition algorithms, for both problems. © 2009 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_0166218X_v158_n12_p1259_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
K-behavior
Proper Helly circular-arc graphs
Circular-arc graph
Clique graphs
Complete solutions
Graph G
Intersection graph
K-behavior
Linear time
Recognition algorithm
Algorithms
Graph theory
Mathematical operators
Graphic methods
spellingShingle Algorithms
Clique graphs
Helly circular-arc graphs
K-behavior
Proper Helly circular-arc graphs
Circular-arc graph
Clique graphs
Complete solutions
Graph G
Intersection graph
K-behavior
Linear time
Recognition algorithm
Algorithms
Graph theory
Mathematical operators
Graphic methods
Lin, M.C.
Soulignac, F.J.
Szwarcfiter, J.L.
The clique operator on circular-arc graphs
topic_facet Algorithms
Clique graphs
Helly circular-arc graphs
K-behavior
Proper Helly circular-arc graphs
Circular-arc graph
Clique graphs
Complete solutions
Graph G
Intersection graph
K-behavior
Linear time
Recognition algorithm
Algorithms
Graph theory
Mathematical operators
Graphic methods
description A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is Helly when the arcs satisfy the Helly Property, while the model is proper Helly when it is simultaneously proper and Helly. A graph admitting a Helly (resp. proper Helly) model is called a Helly (resp. proper Helly) circular-arc graph. The clique graphK (G) of a graph G is the intersection graph of its cliques. The iterated clique graphKi (G) of G is defined by K0 (G) = G and Ki + 1 (G) = K (Ki (G)). In this paper, we consider two problems on clique graphs of circular-arc graphs. The first is to characterize clique graphs of Helly circular-arc graphs and proper Helly circular-arc graphs. The second is to characterize the graph to which a general circular-arc graph K-converges, if it is K-convergent. We propose complete solutions to both problems, extending the partial results known so far. The methods lead to linear time recognition algorithms, for both problems. © 2009 Elsevier B.V. All rights reserved.
format JOUR
author Lin, M.C.
Soulignac, F.J.
Szwarcfiter, J.L.
author_facet Lin, M.C.
Soulignac, F.J.
Szwarcfiter, J.L.
author_sort Lin, M.C.
title The clique operator on circular-arc graphs
title_short The clique operator on circular-arc graphs
title_full The clique operator on circular-arc graphs
title_fullStr The clique operator on circular-arc graphs
title_full_unstemmed The clique operator on circular-arc graphs
title_sort clique operator on circular-arc graphs
url http://hdl.handle.net/20.500.12110/paper_0166218X_v158_n12_p1259_Lin
work_keys_str_mv AT linmc thecliqueoperatoroncirculararcgraphs
AT soulignacfj thecliqueoperatoroncirculararcgraphs
AT szwarcfiterjl thecliqueoperatoroncirculararcgraphs
AT linmc cliqueoperatoroncirculararcgraphs
AT soulignacfj cliqueoperatoroncirculararcgraphs
AT szwarcfiterjl cliqueoperatoroncirculararcgraphs
_version_ 1807319992858836992

Ejemplares similares