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

Katsuhisa Yamanaka - One of the best experts on this subject based on the ideXlab platform.

  • WALCOM - Sequentially Swapping Colored Tokens on Graphs
    WALCOM: Algorithms and Computation, 2017
    Co-Authors: Katsuhisa Yamanaka, Toshiki Saitoh, Yoshio Okamoto, Erik D Demaine, Akira Suzuki, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Ryuhei Uehara
    Abstract:

    We consider a puzzle consisting of colored tokens on an n-Vertex graph, where each token has a distinct Starting Vertex and a set of allowable target vertices for it to reach, and the only allowed transformation is to “sequentially” move the chosen token along a path of the graph by swapping it with other tokens on the path. This puzzle is a variation of the Fifteen Puzzle and is solvable in \(\text{ O }(n^3)\) token-swappings. We thus focus on the problem of minimizing the number of token-swappings to reach the target token-placement. We first give an inapproximability result of this problem, and then show polynomial-time algorithms on trees, complete graphs, and cycles.

  • Swapping labeled tokens on graphs
    Theoretical Computer Science, 2015
    Co-Authors: Katsuhisa Yamanaka, Masashi Kiyomi, Toshiki Saitoh, Jun Kawahara, Yoshio Okamoto, Erik D Demaine, Akira Suzuki, Kei Uchizawa
    Abstract:

    Consider a puzzle consisting of n tokens on an n-Vertex graph, where each token has a distinct Starting Vertex and a distinct target Vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O ( n 2 ) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.

  • FUN - Swapping Labeled Tokens on Graphs
    Lecture Notes in Computer Science, 2014
    Co-Authors: Katsuhisa Yamanaka, Masashi Kiyomi, Toshiki Saitoh, Jun Kawahara, Yoshio Okamoto, Erik D Demaine, Akira Suzuki, Kei Uchizawa
    Abstract:

    Consider a puzzle consisting of n tokens on an n-Vertex graph, where each token has a distinct Starting Vertex and a distinct target Vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n 2) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.

Kei Uchizawa - One of the best experts on this subject based on the ideXlab platform.

  • Swapping labeled tokens on graphs
    Theoretical Computer Science, 2015
    Co-Authors: Katsuhisa Yamanaka, Masashi Kiyomi, Toshiki Saitoh, Jun Kawahara, Yoshio Okamoto, Erik D Demaine, Akira Suzuki, Kei Uchizawa
    Abstract:

    Consider a puzzle consisting of n tokens on an n-Vertex graph, where each token has a distinct Starting Vertex and a distinct target Vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O ( n 2 ) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.

  • FUN - Swapping Labeled Tokens on Graphs
    Lecture Notes in Computer Science, 2014
    Co-Authors: Katsuhisa Yamanaka, Masashi Kiyomi, Toshiki Saitoh, Jun Kawahara, Yoshio Okamoto, Erik D Demaine, Akira Suzuki, Kei Uchizawa
    Abstract:

    Consider a puzzle consisting of n tokens on an n-Vertex graph, where each token has a distinct Starting Vertex and a distinct target Vertex it wants to reach, and the only allowed transformation is to swap the tokens on adjacent vertices. We prove that every such puzzle is solvable in O(n 2) token swaps, and thus focus on the problem of minimizing the number of token swaps to reach the target token placement. We give a polynomial-time 2-approximation algorithm for trees, and using this, obtain a polynomial-time 2α-approximation algorithm for graphs whose tree α-spanners can be computed in polynomial time. Finally, we show that the problem can be solved exactly in polynomial time on complete bipartite graphs.

Mauricio Kischinhevsky - One of the best experts on this subject based on the ideXlab platform.

  • ICCSA (1) - Finding a Starting Vertex for the Reverse Cuthill-McKee Method for Bandwidth Reduction: A Comparative Analysis Using Asymmetric Matrices
    Computational Science and Its Applications – ICCSA 2018, 2018
    Co-Authors: Sanderson L. Gonzaga De Oliveira, Diogo T. Robaina, Alexandre A A M De Abreu, Mauricio Kischinhevsky
    Abstract:

    The need to find pseudo-peripheral vertices arises from many methods for ordering sparse matrix equations. Several algorithms have been proposed to find proper Starting vertices to be used in conjunction with heuristics for bandwidth reductions since the 1970s. This paper reviews the main algorithms for the identification of pseudo-peripheral vertices and selects seven out of these algorithms as potentially being the most promising low-cost methods for solving the problem of finding a proper pseudo-peripheral Vertex in a graph. This work evaluates these seven low-cost methods. Extensive experiments among these algorithms in conjunction with the reverse Cuthill-McKee method applied to a large set of standard benchmark instances suggest that Pachl’s algorithm is a suitable alternative for reducing the bandwidth of matrices with asymmetric sparsity patterns.

  • ICCS (3) - A Modified Bandwidth Reduction Heuristic Based on the WBRA and George-Liu Algorithm
    Lecture Notes in Computer Science, 2018
    Co-Authors: Sanderson L. Gonzaga De Oliveira, Guilherme Oliveira Chagas, Diogo T. Robaina, Diego N. Brandão, Mauricio Kischinhevsky
    Abstract:

    This paper presents a modified heuristic based on the Wonder Bandwidth Reduction Algorithm with Starting Vertex given by the George-Liu algorithm. The results are obtained on a dataset of instances taken from the SuiteSparse matrix collection when solving linear systems using the zero-fill incomplete Cholesky-preconditioned conjugate gradient method. The numerical results show that the improved Vertex labeling heuristic compares very favorably in terms of efficiency and performance with the well-known GPS algorithm for bandwidth and profile reductions.

  • finding a Starting Vertex for the reverse cuthill mckee method for bandwidth reduction a comparative analysis using asymmetric matrices
    International Conference on Computational Science and Its Applications, 2018
    Co-Authors: Sanderson Gonzaga L De Oliveira, Diogo T. Robaina, Alexandre A A M De Abreu, Mauricio Kischinhevsky
    Abstract:

    The need to find pseudo-peripheral vertices arises from many methods for ordering sparse matrix equations. Several algorithms have been proposed to find proper Starting vertices to be used in conjunction with heuristics for bandwidth reductions since the 1970s. This paper reviews the main algorithms for the identification of pseudo-peripheral vertices and selects seven out of these algorithms as potentially being the most promising low-cost methods for solving the problem of finding a proper pseudo-peripheral Vertex in a graph. This work evaluates these seven low-cost methods. Extensive experiments among these algorithms in conjunction with the reverse Cuthill-McKee method applied to a large set of standard benchmark instances suggest that Pachl’s algorithm is a suitable alternative for reducing the bandwidth of matrices with asymmetric sparsity patterns.

B. T. Stadler - One of the best experts on this subject based on the ideXlab platform.

  • Evolutionary Dynamics on Graphs - the Effect of Graph Structure and Initial Placement on Mutant Spread
    Journal of Statistical Theory and Practice, 2011
    Co-Authors: Mark Broom, Jan Rychtář, B. T. Stadler
    Abstract:

    We study the stochastic birth-death process in a finite and structured population and analyze how the fixation probability of a mutant depends on its initial placement. In particular, we study how the fixation probability depends on the degree of the Vertex where the mutant is introduced, and which vertices are its neighbours. We find that within a fixed graph, the fixation probability of a mutant has a negative correlation with the degree of the Starting Vertex. For a general mutant fitness r , we give approximations of relative fixation probabilities in terms of the fixation probabilities of neighbours which will be useful for considering graphs of relatively simple structure but many vertices, for instance of the small world network type, and compare our approximations to simulation results. Further, we explore which types of graphs are conducive to mutant fixation and which are not. We find a high positive correlation between a fixation probability of a randomly placed mutant and the variation of Vertex degrees on that graph.

Reid Andersen - One of the best experts on this subject based on the ideXlab platform.

  • Using PageRank to Locally Partition a Graph
    Internet Mathematics, 2020
    Co-Authors: Reid Andersen, Fan Chung, Kevin J. Lang
    Abstract:

    A local graph partitioning algorithm finds a cut near a specified Starting Vertex, with a running time that depends largely on the size of the small side of the cut, rather than the size of the input graph. In this paper, we present a local partitioning algorithm using a variation of PageRank with a specified Starting distribution. We derive a mixing result for PageRank vectors similar to that for random walks, and we show that the ordering of the vertices produced by a PageRank vector reveals a cut with small conductance. In particular, we show that for any set C with conductance Φ and volume k, a PageRank vector with a certain Starting distribution can be used to produce a set with conductance . We present an improved algorithm for computing approximate PageRank vectors, which allows us to find such a set in time proportional to its size. In particular, we can find a cut with conductance at most ϕ, whose small side has volume at least 2 b , in time O(2 b log2 m/ϕ 2) where m is the number of edges in the...

  • A local algorithm for finding dense subgraphs
    ACM Transactions on Algorithms, 2010
    Co-Authors: Reid Andersen
    Abstract:

    We describe a local algorithm for finding subgraphs with high density, according to a measure of density introduced by Kannan and Vinay [1999]. The algorithm takes as input a bipartite graph G, a Starting Vertex v, and a parameter k, and outputs an induced subgraph of G. It is local in the sense that it does not examine the entire input graph; instead, it adaptively explores a region of the graph near the Starting Vertex. The running time of the algorithm is bounded by O(Δ k2), which depends on the maximum degree Δ, but is otherwise independent of the graph. We prove the following approximation guarantee: for any subgraph S with k′ vertices and density θ, there exists a set S′ ⊆ S for which the algorithm outputs a subgraph with density Ω(θ/log Δ) whenever v i S′ and k ≥ k′. We prove that S′ contains at least half of the edges in S.

  • SODA - A local algorithm for finding dense subgraphs
    2008
    Co-Authors: Reid Andersen
    Abstract:

    A local graph algorithm is one that searches for an approximation of the best solution near a specified Starting Vertex, and has a running time independent of the size of the graph. Recently, local algorithms have been developed for graph partitioning and clustering. In this paper, we present a local algorithm for finding dense subgraphs of bipartite graphs, according to the measure of density proposed by Kannan and Vinay. The algorithm takes as input a bipartite graph with a specified Starting Vertex, and attempts to find a dense subgraph near that Vertex. We prove the following local approximation guarantee for the algorithm. For any subgraph S with k vertices and density θ, there is a large set of Starting vertices within S for which the algorithm produces a subgraph with density Ω(θ/log Δ), where Δ is the maximum degree. The running time of the algorithm is O(Δk2), independent of the number of vertices in the graph.

  • A Local Algorithm for Finding Dense Subgraphs
    arXiv: Data Structures and Algorithms, 2007
    Co-Authors: Reid Andersen
    Abstract:

    We present a local algorithm for finding dense subgraphs of bipartite graphs, according to the definition of density proposed by Kannan and Vinay. Our algorithm takes as input a bipartite graph with a specified Starting Vertex, and attempts to find a dense subgraph near that Vertex. We prove that for any subgraph S with k vertices and density theta, there are a significant number of Starting vertices within S for which our algorithm produces a subgraph S' with density theta / O(log n) on at most O(D k^2) vertices, where D is the maximum degree. The running time of the algorithm is O(D k^2), independent of the number of vertices in the graph.

  • Local Graph Partitioning using PageRank Vectors
    2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), 2006
    Co-Authors: Reid Andersen, Fan Chung, Kevin Lang
    Abstract:

    A local graph partitioning algorithm finds a cut near a specified Starting Vertex, with a running time that depends largely on the size of the small side of the cut, rather than the size of the input graph. In this paper, we present a local partitioning algorithm using a variation of PageRank with a specified Starting distribution. We derive a mixing result for PageRank vectors similar to that for random walks, and show that the ordering of the vertices produced by a PageRank vector reveals a cut with small conductance. In particular, we show that for any set C with conductance Phi and volume k, a PageRank vector with a certain Starting distribution can be used to produce a set with conductance (O(radic(Phi log k)). We present an improved algorithm for computing approximate PageRank vectors, which allows us to find such a set in time proportional to its size. In particular, we can find a cut with conductance at most oslash, whose small side has volume at least 2b in time O(2 log m/(2b log2 m/oslash2) where m is the number of edges in the graph. By combining small sets found by this local partitioning algorithm, we obtain a cut with conductance oslash and approximately optimal balance in time O(m log4 m/oslash)