5 documentos corresponden a la consulta.
Palabras contadas: circular: 66, arc: 131, graphs: 152
Lin, M.C. - Szwarcfiter, J.L.
Discrete Math 2009;309(18):5618-5635
2009
Temas: 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
Descripción: 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.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Bonomo, F.
Discrete Math 2006;306(6):595-597
2006
Temas: Helly circular-arc graphs - Self-clique graphs - Inclusions - Helly circular-arc graphs - Self-clique graphs - Graph theory
Descripción: A clique in a graph is a complete subgraph maximal under inclusion. The clique graph of a graph is the intersection graph of its cliques. A graph is self-clique when it is isomorphic to its clique graph. A circular-arc graph is the intersection graph of a family of arcs of a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. In this note, we describe all the self-clique Helly circular-arc graphs. © 2006 Elsevier B.V. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Durán, G. - Lin, M.C. - Mera, S. - Szwarcfiter, J.L.
Discrete Appl Math 2006;154(13 SPEC ISS):1783-1790
2006
Temas: Algorithms - Circular-arc graphs - Clique-independent sets - Helly circular-arc graphs - Algorithms - Computational complexity - Computational methods - Mathematical models - Set theory - Circular-arc graphs
Descripción: Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Lin, M.C. - Soulignac, F.J. - Szwarcfiter, J.L.
Discrete Appl Math 2010;158(12):1259-1267
2010
Temas: 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
Descripción: 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.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Lin, M.C. - Rautenbach, D. - Soulignac, F.J. - Szwarcfiter, J.L.
Discrete Appl Math 2011;159(7):621-627
2011
Temas: Circulant graph - Circular arc graph - Cycle - Distance graph - Interval graph - Path - Circulant graphs - Circular-arc graph - Cycle - Distance graph
Descripción: In 1988, Golumbic and Hammer characterized the powers of cycles, relating them to circular arc graphs. We extend their results and propose several further structural characterizations for both powers of cycles and powers of paths. The characterizations lead to linear-time recognition algorithms of these classes of graphs. Furthermore, as a generalization of powers of cycles, powers of paths, and even of the well-known circulant graphs, we consider distance graphs. While the colorings of these graphs have been intensively studied, the recognition problem has been so far neglected. We propose polynomial-time recognition algorithms for these graphs under additional restrictions. © 2010 Elsevier B.V. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo