The Experts below are selected from a list of 324 Experts worldwide ranked by ideXlab platform

Jayme Luiz Szwarcfiter - One of the best experts on this subject based on the ideXlab platform.

  • Normal Helly Circular-Arc graphs and its subclasses
    Discrete Applied Mathematics, 2013
    Co-Authors: Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter
    Abstract:

    A Helly Circular-Arc model M = (C,A) is a circle C together with a Helly family \A of Arcs of C. If no Arc is contained in any other, then M is a proper Helly Circular-Arc model, if every Arc has the same length, then M is a unit Helly Circular-Arc model, and if there are no two Arcs covering the circle, then M is a normal Helly Circular-Arc model. A Helly (resp. proper Helly, unit Helly, normal Helly) Circular-Arc graph is the intersection graph of the Arcs of a Helly (resp. proper Helly, unit Helly, normal Helly) Circular-Arc model. In this article we study these subclasses of Helly Circular-Arc graphs. We show natural generalizations of several properties of (proper) interval graphs that hold for some of these Helly Circular-Arc subclasses. Next, we describe characterizations for the subclasses of Helly Circular-Arc graphs, including forbidden induced subgraphs characterizations. These characterizations lead to efficient algorithms for recognizing graphs within these classes. Finally, we show how do these classes of graphs relate with straight and round digraphs.Comment: 39 pages, 13 figures. A previous version of the paper (entitled Proper Helly Circular-Arc Graphs) appeared at WG'0

  • Normal Helly Circular-Arc graphs and its subclasses
    Discrete Applied Mathematics, 2012
    Co-Authors: Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter
    Abstract:

    A Helly Circular-Arc model M=(C,A) is a circle C together with a Helly family A of Arcs of C. If no Arc is contained in any other, then M is a proper Helly Circular-Arc model, if every Arc has the same length, then M is a unit Helly Circular-Arc model, and if there are no two Arcs covering the circle, then M is a normal Helly Circular-Arc model. A Helly (resp. proper Helly, unit Helly, normal Helly) Circular-Arc graph is the intersection graph of the Arcs of a Helly (resp. proper Helly, unit Helly, normal Helly) Circular-Arc model. In this article we study these subclasses of Helly Circular-Arc graphs. We show natural generalizations of several properties of (proper) interval graphs that hold for some of these Helly Circular-Arc subclasses. Next, we describe characterizations for the subclasses of Helly Circular-Arc graphs, including forbidden induced subgraphs characterizations. These characterizations lead to efficient algorithms for recognizing graphs within these classes. Finally, we show how these classes of graphs relate with straight and round digraphs.

  • The clique operator on Circular-Arc graphs
    Discrete Applied Mathematics, 2010
    Co-Authors: Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter
    Abstract:

    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 graphK^i(G) of G is defined by K^0(G)=G and K^i^+^1(G)=K(K^i(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.

  • Linear-Time Recognition of Helly Circular-Arc Models and Graphs
    Algorithmica, 2009
    Co-Authors: Benson Joeris, Min Chih Lin, Ross M. Mcconnell, Jeremy P. Spinrad, Jayme Luiz Szwarcfiter
    Abstract:

    A Circular-Arc model ℳ is a circle C together with a collection $\mathcal{A}$ of Arcs of C. If $\mathcal{A}$ satisfies the Helly Property then ℳ is a Helly Circular-Arc model. A (Helly) Circular-Arc graph is the intersection graph of a (Helly) Circular-Arc model. Circular-Arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly Circular-Arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n 3). In this article, we describe different characterizations for Helly Circular-Arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound.

  • Characterizations and recognition of Circular-Arc graphs and subclasses: A survey
    Discrete Mathematics, 2009
    Co-Authors: Min Chih Lin, Jayme Luiz Szwarcfiter
    Abstract:

    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.

Min Chih Lin - One of the best experts on this subject based on the ideXlab platform.

  • Normal Helly Circular-Arc graphs and its subclasses
    Discrete Applied Mathematics, 2013
    Co-Authors: Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter
    Abstract:

    A Helly Circular-Arc model M = (C,A) is a circle C together with a Helly family \A of Arcs of C. If no Arc is contained in any other, then M is a proper Helly Circular-Arc model, if every Arc has the same length, then M is a unit Helly Circular-Arc model, and if there are no two Arcs covering the circle, then M is a normal Helly Circular-Arc model. A Helly (resp. proper Helly, unit Helly, normal Helly) Circular-Arc graph is the intersection graph of the Arcs of a Helly (resp. proper Helly, unit Helly, normal Helly) Circular-Arc model. In this article we study these subclasses of Helly Circular-Arc graphs. We show natural generalizations of several properties of (proper) interval graphs that hold for some of these Helly Circular-Arc subclasses. Next, we describe characterizations for the subclasses of Helly Circular-Arc graphs, including forbidden induced subgraphs characterizations. These characterizations lead to efficient algorithms for recognizing graphs within these classes. Finally, we show how do these classes of graphs relate with straight and round digraphs.Comment: 39 pages, 13 figures. A previous version of the paper (entitled Proper Helly Circular-Arc Graphs) appeared at WG'0

  • Normal Helly Circular-Arc graphs and its subclasses
    Discrete Applied Mathematics, 2012
    Co-Authors: Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter
    Abstract:

    A Helly Circular-Arc model M=(C,A) is a circle C together with a Helly family A of Arcs of C. If no Arc is contained in any other, then M is a proper Helly Circular-Arc model, if every Arc has the same length, then M is a unit Helly Circular-Arc model, and if there are no two Arcs covering the circle, then M is a normal Helly Circular-Arc model. A Helly (resp. proper Helly, unit Helly, normal Helly) Circular-Arc graph is the intersection graph of the Arcs of a Helly (resp. proper Helly, unit Helly, normal Helly) Circular-Arc model. In this article we study these subclasses of Helly Circular-Arc graphs. We show natural generalizations of several properties of (proper) interval graphs that hold for some of these Helly Circular-Arc subclasses. Next, we describe characterizations for the subclasses of Helly Circular-Arc graphs, including forbidden induced subgraphs characterizations. These characterizations lead to efficient algorithms for recognizing graphs within these classes. Finally, we show how these classes of graphs relate with straight and round digraphs.

  • The clique operator on Circular-Arc graphs
    Discrete Applied Mathematics, 2010
    Co-Authors: Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter
    Abstract:

    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 graphK^i(G) of G is defined by K^0(G)=G and K^i^+^1(G)=K(K^i(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.

  • Linear-Time Recognition of Helly Circular-Arc Models and Graphs
    Algorithmica, 2009
    Co-Authors: Benson Joeris, Min Chih Lin, Ross M. Mcconnell, Jeremy P. Spinrad, Jayme Luiz Szwarcfiter
    Abstract:

    A Circular-Arc model ℳ is a circle C together with a collection $\mathcal{A}$ of Arcs of C. If $\mathcal{A}$ satisfies the Helly Property then ℳ is a Helly Circular-Arc model. A (Helly) Circular-Arc graph is the intersection graph of a (Helly) Circular-Arc model. Circular-Arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear-time recognition algorithms have been described both for the general class and for some of its subclasses. However, for Helly Circular-Arc graphs, the best recognition algorithm is that by Gavril, whose complexity is O(n 3). In this article, we describe different characterizations for Helly Circular-Arc graphs, including a characterization by forbidden induced subgraphs for the class. The characterizations lead to a linear-time recognition algorithm for recognizing graphs of this class. The algorithm also produces certificates for a negative answer, by exhibiting a forbidden subgraph of it, within this same bound.

  • Characterizations and recognition of Circular-Arc graphs and subclasses: A survey
    Discrete Mathematics, 2009
    Co-Authors: Min Chih Lin, Jayme Luiz Szwarcfiter
    Abstract:

    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.

Yahav Nussbaum - One of the best experts on this subject based on the ideXlab platform.

  • Certifying algorithms for recognizing proper Circular-Arc graphs and unit Circular-Arc graphs
    Discrete Applied Mathematics, 2009
    Co-Authors: Haim Kaplan, Yahav Nussbaum
    Abstract:

    We give two new linear-time algorithms, one for recognizing proper Circular-Arc graphs and the other for recognizing unit Circular-Arc graphs. Both algorithms provide either a model for the input graph, or a certificate that proves that such a model does not exist and can be authenticated in O(n) time. No other previous algorithm for each of these two graph classes provides a certificate for its result.

  • WG - From a Circular-Arc Model to a Proper Circular-Arc Model
    Graph-Theoretic Concepts in Computer Science, 2008
    Co-Authors: Yahav Nussbaum
    Abstract:

    We are given a Circular-Arc graph, represented by a Circular-Arc model; our goal is to decide whether the graph is a proper Circular-Arc graph. We do so in time linear in the number of vertices of the graph, regardless of the number of edges which may be quadratic in the number of vertices. For every input graph, we either provide a proper Circular-Arc model for the graph, or a forbidden subgraph induced in the graph.

  • Recognition of Circular-Arc Graphs and Some Subclasses
    2007
    Co-Authors: Yahav Nussbaum
    Abstract:

    In this work we present three new recognition algorithms for Circular-Arc graphs and for two subclasses of this graph class. We give a linear-time recognition algorithm for Circular-Arc graphs based on the algorithm of Eschen and Spinrad [ES93, Esc97]. Our algorithm is simpler than the earlier linear-time recognition algorithm of McConnell [McC03], which is the only linear time recognition algorithm previously known. We give new characterizations of proper Circular-Arc graphs and of unit Circular-Arc graphs which are based on characterizations of Tucker [Tuc71, Tuc74]. These characterizations lead to two new linear-time algorithms for recognizing proper Circular-Arc graphs and for recognizing unit Circular-Arc graphs. Both algorithms either provide a model for the input graph, or a certificate that such a model does not exist. No other previous algorithm for each of these two graph classes provides a certificate for its result.

  • Certifying algorithms for recognizing proper Circular-Arc graphs and unit Circular-Arc graphs
    Lecture Notes in Computer Science, 2006
    Co-Authors: Haim Kaplan, Yahav Nussbaum
    Abstract:

    We give two new algorithms for recognizing proper Circular-Arc graphs and unit Circular-Arc graphs. The algorithms either provide a model for the input graph, or a certificate that proves that such a model does not exist and can be authenticated in O(n) time.

Haim Kaplan - One of the best experts on this subject based on the ideXlab platform.

Guillermo Durán - One of the best experts on this subject based on the ideXlab platform.

  • Balancedness of subclasses of Circular-Arc graphs
    Discrete Mathematics and Theoretical Computer Science, 2014
    Co-Authors: Flavia Bonomo, Guillermo Durán, Martín D. Safe, Annegret K. Wagler
    Abstract:

    A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, but no characterization by mininal forbidden induced subgraphs is known, not even for the case of Circular-Arc graphs. A Circular-Arc graph is the intersection graph of a family of Arcs on a circle. In this work, we characterize when a given graph G is balanced in terms of minimal forbidden induced subgraphs, by restricting the analysis to the case where G belongs to certain classes of Circular-Arc graphs, including Helly Circular-Arc graphs, claw-free Circular-Arc graphs, and gem-free Circular-Arc graphs. In the case of gem-free Circular-Arc graphs, analogous characterizations are derived for two superclasses of balanced graphs: clique-perfect graphs and coordinated graphs.

  • partial characterizations of Circular Arc graphs
    Journal of Graph Theory, 2009
    Co-Authors: Flavia Bonomo, Guillermo Durán, Luciano N. Grippo, Martín D. Safe
    Abstract:

    A Circular-Arc graph is the intersection graph of a family of Arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize Circular-Arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P4 -free graphs, paw-free graphs, claw-free chordal graphs and diamond-free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009

  • Partial Characterizations of Circular-Arc Graphs
    Electronic Notes in Discrete Mathematics, 2008
    Co-Authors: Flavia Bonomo, Guillermo Durán, Luciano N. Grippo, Martín D. Safe
    Abstract:

    Abstract A Circular-Arc graph is the intersection graph of a family of Arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize Circular-Arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to the following classes: diamond-free graphs, P 4 -free graphs, paw-free graphs, and claw-free chordal graphs.

  • Polynomial time recognition of unit Circular-Arc graphs
    Journal of Algorithms, 2006
    Co-Authors: Guillermo Durán, Ross M. Mcconnell, Agustín Gravano, Jeremy P. Spinrad, Alan Tucker
    Abstract:

    We present an efficient algorithm for recognizing unit Circular-Arc (UCA) graphs, based on a characterization theorem for UCA graphs proved by Tucker in the seventies. Given a proper Circular-Arc (PCA) graph G, the algorithm starts from a PCA model for G, removes all its circle-covering pairs of Arcs and determines whether G is a UCA graph. We also give an O(N) time bound for Tucker's 3/2-approximation algorithm for coloring Circular-Arc graphs with N vertices, when a Circular-Arc model is given.

  • On some subclasses of Circular-Arc graphs
    2002
    Co-Authors: Guillermo Durán
    Abstract:

    The intersection graph of a family of Arcs on a circle is called a Circular-Arc graph. This class of graphs admits some interesting subclasses: proper Circular-Arc graphs, unit Circular-Arc graphs, Helly Circular-Arc graphs and clique-Helly Circular-Arc graphs. In this paper, all possible intersections of these subclasses are studied. There are thirteen regions. Twelve of these are nonempty, and we construct a minimal graph in each of them. Our main result is that the thirteenth region is empty, namely we prove that among proper but no unit Circular-Arc graphs, every clique-Helly Circular-Arc graph is also a Helly Circular-Arc graph.