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

Takeaki Uno - One of the best experts on this subject based on the ideXlab platform.

  • efficient enumeration of maximal k degenerate induced subGraphs of a Chordal Graph
    Theoretical Computer Science, 2020
    Co-Authors: Alessio Conte, Mamadou Moustapha Kante, Yota Otachi, Takeaki Uno, Kunihiro Wasa
    Abstract:

    Abstract In this paper we consider the problem of listing the maximal k-degenerate induced subGraphs of a Chordal Graph, and propose an output-sensitive algorithm using delay O ( m ⋅ ω ( G ) ) for any n-vertex Chordal Graph with m edges, where ω ( G ) ≤ n is the maximum size of a clique in G. Degeneracy is a well known sparsity measure, and k-degenerate subGraphs are a notion of sparse subGraphs, which generalizes other problems such as independent sets (0-degenerate subGraphs) and forests (1-degenerate subGraphs). Many efficient enumeration algorithms are designed by solving the so-called Extension problem, which asks whether there exists a maximal solution containing a given set of nodes, but no node from a forbidden set. We show that solving this problem is np -complete for maximal k-degenerate induced subGraphs, motivating the need for additional techniques.

  • efficient enumeration of maximal k degenerate subGraphs in a Chordal Graph
    Computing and Combinatorics Conference, 2017
    Co-Authors: Alessio Conte, Mamadou Moustapha Kante, Yota Otachi, Takeaki Uno, Kunihiro Wasa
    Abstract:

    In this paper, we consider the problem of listing the maximal k-degenerate induced subGraphs of a Chordal Graph, and propose an output-sensitive algorithm using delay \(O(m\cdot \omega (G))\) for any n-vertex Chordal Graph with m edges, where \(\omega (G) \le n\) is the maximum size of a clique in G. The problem generalizes that of enumerating maximal independent sets and maximal induced forests, which correspond to respectively 0-degenerate and 1-degenerate subGraphs.

  • enumeration of the perfect sequences of a Chordal Graph
    Theoretical Computer Science, 2010
    Co-Authors: Yasuko Matsui, Ryuhei Uehara, Takeaki Uno
    Abstract:

    A Graph is Chordal if and only if it has no chordless cycle of length more than three. The set of maximal cliques in a Chordal Graph admits special tree structures called clique trees. A perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. This paper addresses the problem of enumerating all the perfect sequences. Although this problem has statistical applications, no efficient algorithm has been proposed. There are two difficulties with developing this type of algorithm. First, a Chordal Graph does not generally have a unique clique tree. Second, a perfect sequence can normally be generated by two or more distinct clique trees. Thus it is hard using a straightforward algorithm to generate perfect sequences from each possible clique tree. In this paper, we propose a method to enumerate perfect sequences without constructing clique trees. As a result, we have developed the first polynomial delay algorithm for dealing with this problem. In particular, the time complexity of the algorithm on average is O(1) for each perfect sequence.

  • enumeration of perfect sequences of Chordal Graph
    International Symposium on Algorithms and Computation, 2008
    Co-Authors: Yasuko Matsui, Ryuhei Uehara, Takeaki Uno
    Abstract:

    A Graph is Chordal if and only if it has no chordless cycle of length more than three. The set of maximal cliques in a Chordal Graph admits special tree structures called clique trees. A perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. This paper addresses the problem of enumerating all the perfect sequences. Although this problem has statistical applications, no efficient algorithm has been proposed. There are two difficulties with developing this type of algorithms. First, a Chordal Graph does not generally have a unique clique tree. Second, a perfect sequence can normally be generated by two or more distinct clique trees. Thus it is hard using a straightforward way to generate perfect sequences from each possible clique tree. In this paper, we propose a method to enumerate perfect sequences without constructing clique trees. As a result, we have developed the first polynomial delay algorithm for dealing with this problem. In particular, the time complexity of the algorithm on average is O(1) for each perfect sequence.

  • Counting the number of independent sets in Chordal Graphs
    Journal of Discrete Algorithms, 2008
    Co-Authors: Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara
    Abstract:

    We study some counting and enumeration problems for Chordal Graphs, especially concerning independent sets. We first provide the following efficient algorithms for a Chordal Graph: (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a Chordal Graph can be done in constant time per output. On the other hand, we prove that the following problems for a Chordal Graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a Chordal Graph is NP-hard, and even hard to approximate.

Ryuhei Uehara - One of the best experts on this subject based on the ideXlab platform.

  • enumeration of the perfect sequences of a Chordal Graph
    Theoretical Computer Science, 2010
    Co-Authors: Yasuko Matsui, Ryuhei Uehara, Takeaki Uno
    Abstract:

    A Graph is Chordal if and only if it has no chordless cycle of length more than three. The set of maximal cliques in a Chordal Graph admits special tree structures called clique trees. A perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. This paper addresses the problem of enumerating all the perfect sequences. Although this problem has statistical applications, no efficient algorithm has been proposed. There are two difficulties with developing this type of algorithm. First, a Chordal Graph does not generally have a unique clique tree. Second, a perfect sequence can normally be generated by two or more distinct clique trees. Thus it is hard using a straightforward algorithm to generate perfect sequences from each possible clique tree. In this paper, we propose a method to enumerate perfect sequences without constructing clique trees. As a result, we have developed the first polynomial delay algorithm for dealing with this problem. In particular, the time complexity of the algorithm on average is O(1) for each perfect sequence.

  • enumeration of perfect sequences of Chordal Graph
    International Symposium on Algorithms and Computation, 2008
    Co-Authors: Yasuko Matsui, Ryuhei Uehara, Takeaki Uno
    Abstract:

    A Graph is Chordal if and only if it has no chordless cycle of length more than three. The set of maximal cliques in a Chordal Graph admits special tree structures called clique trees. A perfect sequence is a sequence of maximal cliques obtained by using the reverse order of repeatedly removing the leaves of a clique tree. This paper addresses the problem of enumerating all the perfect sequences. Although this problem has statistical applications, no efficient algorithm has been proposed. There are two difficulties with developing this type of algorithms. First, a Chordal Graph does not generally have a unique clique tree. Second, a perfect sequence can normally be generated by two or more distinct clique trees. Thus it is hard using a straightforward way to generate perfect sequences from each possible clique tree. In this paper, we propose a method to enumerate perfect sequences without constructing clique trees. As a result, we have developed the first polynomial delay algorithm for dealing with this problem. In particular, the time complexity of the algorithm on average is O(1) for each perfect sequence.

  • Counting the number of independent sets in Chordal Graphs
    Journal of Discrete Algorithms, 2008
    Co-Authors: Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara
    Abstract:

    We study some counting and enumeration problems for Chordal Graphs, especially concerning independent sets. We first provide the following efficient algorithms for a Chordal Graph: (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a Chordal Graph can be done in constant time per output. On the other hand, we prove that the following problems for a Chordal Graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a Chordal Graph is NP-hard, and even hard to approximate.

Xiaoqing Yuan - One of the best experts on this subject based on the ideXlab platform.

  • a clique tree algorithm for partitioning a Chordal Graph into transitive subGraphs
    Linear Algebra and its Applications, 1994
    Co-Authors: Barry W Peyton, Alex Pothen, Xiaoqing Yuan
    Abstract:

    A partitioning problem on Chordal Graphs that arises in the solution of sparse triangular systems of equations on parallel computers is considered. Roughly the problem is to partition a Chordal Graph $G$ into the fewest transitively orientable subGraphs over all perfect elimination orderings of $G$, subject to a certain precedence relationship on its vertices. In earlier work, a greedy scheme that solved the problem by eliminating a largest subset of vertices at each step was described, and an algorithm implementing the scheme in time and space linear in the number of edges of the Graph was provided. Here a more efficient greedy scheme, obtained by representing the Chordal Graph in terms of its maximal cliques, which eliminates a subset of the leaf cliques % of the current Graph at each step is described. Several new results about minimal vertex separators in Chordal Graphs, and in particular the concept of a {\em critical separator\/} of a leaf clique, are employed to prove that the new scheme solves the partitioning problem. We provide an algorithm implementing the scheme in time and space linear in the size of the clique tree.

  • partitioning a Chordal Graph into transitive subGraphs for parallel sparse triangular solution
    Partitioning a Chordal Graph into Transitive Subgraphs for Parallel Sparse Triangular Solution*, 1994
    Co-Authors: Barry W Peyton, Alex Pothen, Xiaoqing Yuan
    Abstract:

    A recent approach for solving sparse triangular systems of equations on massively parallel computers employs a factorization of the triangular coefficient matrix to obtain a representation of its inverse in product form. The number of general communication steps required by this approach is proportional to the number of factors in the factorization. The triangular matrix can be symmetrically permuted to minimize the number of factors over suitable classes of permutations, and thereby the complexity of the parallel algorithm can be minimized. Algorithms for minimizing the number of factors over several classes of permutations have been considered in earlier work. Let $F=L+L^T$ denote the symmetric filled matrix corresponding to a Cholesky factor $L$, and let $G_F$ denote the adjacency Graph of $F$. In this paper we consider the problem of minimizing the number of factors over all permutations which preserve the structure of $G_F$. The Graph model of this problem is to partition the vertices $G_F$ into the fewest transitively closed subGraphs over all perfect elimination orderings while satisfying a certain precedence relationship. The solution to this Chordal Graph partitioning problem can be described by a greedy scheme which eliminates a largest permissible subGraph at each step. Further, the subGraph eliminated at each step can be characterized in terms of lengths of chordless paths in the current elimination Graph. This solution relies on several results concerning {\em transitive perfect elimination orderings\/} introduced in this paper. We describe a partitioning algorithm with $\order{|V|+|E|}$ time and space complexity.

  • partitioning a Chordal Graph into transitive subGraphs for parallel sparse triangular solution
    Linear Algebra and its Applications, 1993
    Co-Authors: Barry W Peyton, Alex Pothen, Xiaoqing Yuan
    Abstract:

    Abstract A recent approach for solving sparse triangular systems of equations on massively parallel computers employs a factorization of the triangular coefficient matrix to obtain a representation of its inverse in product form. The number of general communication steps required by this approach is proportional to the number of factors in the factorization. The triangular matrix can be symmetrically permuted to minimize the number of factors over suitable classes of permutations, and thereby the complexity of the parallel algorithm can be minimized. Algorithms for minimizing the number of factors over several classes of permutations have been considered in earlier work. Let F = L + LT denote the symmetric filled matrix corresponding to a Cholesky factor L, and let GF denote the adjacency Graph of F. We consider the problem of minimizing the number of factors over all permutations which preserve the structure of GF. The Graph model of this problem is to partition the vertices GF into the fewest transitively closed subGraphs over all perfect elimination orderings while satisfying a certain precedence relationship. The solution to this Chordal-Graph partitioning problem can be described by a greedy scheme which eliminates a largest permissible subGraph at each step. Further, the subGraph eliminated at each step can be characterized in terms of lengths of chordless paths in the current elimination Graph. This solution relies on several results concerning transitive perfect elimination orderings introduced in this paper. We describe a partitioning algorithm with O (∣V∣ + ∣E∣) time and space complexity.

Anne Berry - One of the best experts on this subject based on the ideXlab platform.

  • Computing a Clique Tree with the Algorithm Maximal Label Search
    Algorithms, 2017
    Co-Authors: Anne Berry, Geneviève Simonet
    Abstract:

    The algorithm MLS (Maximal Label Search) is a Graph search algorithm that generalizes the algorithms Maximum Cardinality Search (MCS), LexicoGraphic Breadth-First Search (LexBFS), LexicoGraphic Depth-First Search (LexDFS) and Maximal Neighborhood Search (MNS). On a Chordal Graph, MLS computes a PEO (perfect elimination ordering) of the Graph. We show how the algorithm MLS can be modified to compute a PMO (perfect moplex ordering), as well as a clique tree and the minimal separators of a Chordal Graph. We give a necessary and sufficient condition on the labeling structure of MLS for the beginning of a new clique in the clique tree to be detected by a condition on labels. MLS is also used to compute a clique tree of the complement Graph, and new cliques in the complement Graph can be detected by a condition on labels for any labeling structure. We provide a linear time algorithm computing a PMO and the corresponding generators of the maximal cliques and minimal separators of the complement Graph. On a non-Chordal Graph, the algorithm MLSM, a Graph search algorithm computing an MEO and a minimal triangulation of the Graph, is used to compute an atom tree of the clique minimal separator decomposition of any Graph.

  • A simple algorithm to generate the minimal separators and the maximal cliques of a Chordal Graph
    Information Processing Letters, 2011
    Co-Authors: Anne Berry, Romain Pogorelcnik
    Abstract:

    We present a simple unified algorithmic process which uses either LexBFS or MCS on a Chordal Graph to generate the minimal separators and the maximal cliques in linear time in a single pass.

  • Graph Extremities Defined by Search Algorithms
    Algorithms, 2010
    Co-Authors: Anne Berry, Jean R.s. Blair, Jean-paul Bordat, Geneviève Simonet
    Abstract:

    Graph search algorithms have exploited Graph extremities, such as the leaves of a tree and the simplicial vertices of a Chordal Graph. Recently, several well-known Graph search algorithms have been collectively expressed as two generic algorithms called MLS and MLSM. In this paper, we investigate the properties of the vertex that is numbered 1 by MLS on a Chordal Graph and by MLSM on an arbitrary Graph. We explain how this vertex is an extremity of the Graph. Moreover, we show the remarkable property that the minimal separators included in the neighborhood of this vertex are totally ordered by inclusion

  • Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings
    SIAM Journal on Discrete Mathematics, 2009
    Co-Authors: Anne Berry, Richard Krueger, Geneviève Simonet
    Abstract:

    Many Graph search algorithms use a vertex labeling to compute an ordering of the vertices. We examine such algorithms which compute a peo (perfect elimination ordering) of a Chordal Graph, and corresponding algorithms which compute an meo (minimal elimination ordering) of a non-Chordal Graph, an ordering used to compute a minimal triangulation of the input Graph. \par We express all known peo-computing search algorithms as instances of a generic algorithm called MLS (Maximal Label Search) and generalize Algorithm MLS into CompMLS, which can compute any peo. \par We then extend these algorithms to versions which compute an meo, and likewise generalize all known meo-computing search algorithms. We show that not all minimal triangulations can be computed by such a Graph search, and, more surprisingly, that all these search algorithms compute the same set of minimal triangulations, even though the computed meos are different. \par Finally, we present a complexity analysis of these algorithms.

  • Faster Dynamic Algorithms for Chordal Graphs, and an Application to Phylogeny
    2005
    Co-Authors: Anne Berry, Alain Sigayret, Jeremy P. Spinrad
    Abstract:

    We improve the current complexities for maintaining a Chordal Graph by starting with an empty Graph and repeatedly adding or deleting edges.

Feodor F Dragan - One of the best experts on this subject based on the ideXlab platform.

  • an eccentricity 2 approximating spanning tree of a Chordal Graph is computable in linear time
    Information Processing Letters, 2020
    Co-Authors: Feodor F Dragan
    Abstract:

    Abstract It is known that every Chordal Graph G = ( V , E ) has a spanning tree T such that, for every vertex v ∈ V , e c c T ( v ) ≤ e c c G ( v ) + 2 holds (here e c c G ( v ) : = max ⁡ { d G ( v , u ) : u ∈ V } is the eccentricity of v in G). We show that such a spanning tree can be computed in linear time for every Chordal Graph. As a byproduct, we get that the eccentricities of all vertices of a Chordal Graph G can be computed in linear time with an additive one-sided error of at most 2, i.e., after a linear time preprocessing, for every vertex v of G, one can compute in O ( 1 ) time an estimate e ˆ ( v ) of its eccentricity e c c G ( v ) such that e c c G ( v ) ≤ e ˆ ( v ) ≤ e c c G ( v ) + 2 .

  • a linear time algorithm for finding a central vertex of a Chordal Graph
    European Symposium on Algorithms, 1994
    Co-Authors: Victor Chepoi, Feodor F Dragan
    Abstract:

    In a Graph G=(V, E), the eccentricity e(v) of a vertex v is max{d(v, u)∶u ∈ V}. The center of a Graph is the set of vertices with minimum eccentricity. A Graph G is Chordal if every cycle of length at least four has a chord. We present an algorithm which computes in linear time a central vertex of a Chordal Graph. The algorithm uses the metric properties of Chordal Graphs and Tarjan and Yannakakis linear-time test for Graph Chordality.