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

Kanat Tangwongsan - One of the best experts on this subject based on the ideXlab platform.

  • work efficient batch incremental Minimum Spanning Trees with applications to the sliding window model
    ACM Symposium on Parallel Algorithms and Architectures, 2020
    Co-Authors: Daniel Anderson, Guy E Blelloch, Kanat Tangwongsan
    Abstract:

    Algorithms for dynamically maintaining Minimum Spanning Trees (MSTs) have received much attention in both the parallel and sequential settings. While previous work has given optimal algorithms for dense graphs, all existing parallel batch-dynamic algorithms perform polynomial work per update in the worst case for sparse graphs. In this paper, we present the first work-efficient parallel batch-dynamic algorithm for incremental MST, which can insert l edges in O(l log(1+n/l) work in expectation and O(polylog(n)) span w.h.p. The key ingredient of our algorithm is an algorithm for constructing a compressed path tree of an edge-weighted tree, which is a smaller tree that contains all pairwise heaviest edges between a given set of marked vertices. Using our batch-incremental MST algorithm, we demonstrate a range of applications that become efficiently solvable in parallel in the sliding-window model, such as graph connectivity, approximate MSTs, testing bipartiteness, k-certificates, cycle-freeness, and maintaining sparsifiers.

  • work efficient batch incremental Minimum Spanning Trees with applications to the sliding window model
    arXiv: Data Structures and Algorithms, 2020
    Co-Authors: Daniel Anderson, Guy E Blelloch, Kanat Tangwongsan
    Abstract:

    Algorithms for dynamically maintaining Minimum Spanning Trees (MSTs) have received much attention in both the parallel and sequential settings. While previous work has given optimal algorithms for dense graphs, all existing parallel batch-dynamic algorithms perform polynomial work per update in the worst case for sparse graphs. In this paper, we present the first work-efficient parallel batch-dynamic algorithm for incremental MST, which can insert $\ell$ edges in $O(\ell \log(1+n/\ell))$ work in expectation and $O(\text{polylog}(n))$ span w.h.p. The key ingredient of our algorithm is an algorithm for constructing a compressed path tree of an edge-weighted tree, which is a smaller tree that contains all pairwise heaviest edges between a given set of marked vertices. Using our batch-incremental MST algorithm, we demonstrate a range of applications that become efficiently solvable in parallel in the sliding-window model, such as graph connectivity, approximate MSTs, testing bipartiteness, $k$-certificates, cycle-freeness, and maintaining sparsifiers.

Pankaj K Agarwal - One of the best experts on this subject based on the ideXlab platform.

  • parametric and kinetic Minimum Spanning Trees
    Foundations of Computer Science, 1998
    Co-Authors: Pankaj K Agarwal, David Eppstein, Leonidas J Guibas, M R Henzinger
    Abstract:

    We consider the parametric Minimum Spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter /spl lambda/ and wish to compute the sequence of Minimum Spanning Trees generated as /spl lambda/ varies. We also consider the kinetic Minimum Spanning tree problem, in which /spl lambda/ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n/sup 2/3/log/sup 4/3/) per combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup 1/2/log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for planar graphs with weight changes but no insertions or deletions.

  • euclidean Minimum Spanning Trees and bichromatic closest pairs
    Discrete and Computational Geometry, 1991
    Co-Authors: Pankaj K Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, Emo Welzl
    Abstract:

    We present an algorithm to compute a Euclidean Minimum Spanning tree of a given setS ofN points inEd in timeO(Fd(N,N) logdN), whereFd(n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inEd. IfFd(N,N)=Ω(N1+?), for some fixed ?>0, then the running time improves toO(Fd(N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)2/3+m log2n+n log2m) inE3, which yields anO(N4/3 log4/3N) expected time, algorithm for computing a Euclidean Minimum Spanning tree ofN points inE3. Ind?4 dimensions we obtain expected timeO((nm)1?1/([d/2]+1)+?+m logn+n logm) for the bichromatic closest pair problem andO(N2?2/([d/2]+1)?) for the Euclidean Minimum Spanning tree problem, for any positive ?.

Subhash Suri - One of the best experts on this subject based on the ideXlab platform.

  • stochastic Minimum Spanning Trees in euclidean spaces
    Symposium on Computational Geometry, 2011
    Co-Authors: Pegah Kamousi, Timothy M Chan, Subhash Suri
    Abstract:

    We study the complexity of geometric Minimum Spanning Trees under a stochastic model of input: Suppose we are given a master set of points s1,s_2,...,sn in d-dimensional Euclidean space, where each point si is active with some independent and arbitrary but known probability pi. We want to compute the expected length of the Minimum Spanning tree (MST) of the active points. This particular form of stochastic problems is motivated by the uncertainty inherent in many sources of geometric data but has not been investigated before in computational geometry to the best of our knowledge. Our main results include the following.We show that the stochastic MST problem is SPHARD for any dimension d ≥ 2. We present a simple fully polynomial randomized approximation scheme (FPRAS) for a metric space, and thus also for any Euclidean space. For d=2, we present two deterministic approximation algorithms: an O(n4)-time constant-factor algorithm, and a PTAS based on a combination of shifted quadTrees and dynamic programming. We show that in a general metric space the tail bounds of the distribution of the MST length cannot be approximated to any multiplicative factor in polynomial time under the assumption that P ≠ NP.In addition to this existential model of stochastic input, we also briefly consider a locational model where each point is present with certainty but its location is probabilistic.

  • transitions in geometric Minimum Spanning Trees
    Symposium on Computational Geometry, 1992
    Co-Authors: Clyde L Monma, Subhash Suri
    Abstract:

    We study some combinatorial and algorithmic problems associated with an arbitrary motion of input points in space. The motivation for such an investigation comes from two different sources:computer modeling andsensitivity analysis. In modeling, the dynamics enters the picture since geometric objects often model physical entities whose positions can change over time. In sensitivity analysis, the motion of the input points might represent uncertainties in the precise location of objects. The main results of the paper deal with state transitions in the Minimum Spanning tree when one or more of the input points move arbitrarily in space. In particular, questions of the following form are addressed: (i) How many different Minimum Spanning Trees can arise if one point moves while the others remain fixed? (ii) When does the Minimum Spanning tree change its topology if all points are allowed to move arbitrarily?

Gopal Pandurangan - One of the best experts on this subject based on the ideXlab platform.

  • a time and message optimal distributed algorithm for Minimum Spanning Trees
    ACM Transactions on Algorithms, 2019
    Co-Authors: Gopal Pandurangan, Peter Robinson, Michele Scquizzato
    Abstract:

    This article presents a randomized (Las Vegas) distributed algorithm that constructs a Minimum Spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in O(D + √ n) time and exchanges O(m) messages (both with high probability), where n is the number of nodes of the network, D is the hop-diameter, and m is the number of edges. This is the first distributed MST algorithm that matches simultaneously the time lower bound of Ω˜(D + √ n) [10] and the message lower bound of Ω (m) [31], which both apply to randomized Monte Carlo algorithms.The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower-bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower-bound graph construction for which any distributed MST algorithm requires both Ω˜(D + √ n) rounds and Ω (m) messages.

  • a time and message optimal distributed algorithm for Minimum Spanning Trees
    Symposium on the Theory of Computing, 2017
    Co-Authors: Gopal Pandurangan, Peter Robinson, Michele Scquizzato
    Abstract:

    This paper presents a randomized (Las Vegas) distributed algorithm that constructs a Minimum Spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in O(D + √n) time and exchanges O(m) messages (both with high probability), where n is the number of nodes of the network, D is the diameter, and m is the number of edges. This is the first distributed MST algorithm that matches simultaneously the time lower bound of Ω(D + √n) [Elkin, SIAM J. Comput. 2006] and the message lower bound of Ω(m) [Kutten et al., J. ACM 2015], which both apply to randomized Monte Carlo algorithms. The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires both Ω(D + √n) rounds and Ω(m) messages.

  • a time and message optimal distributed algorithm for Minimum Spanning Trees
    arXiv: Distributed Parallel and Cluster Computing, 2016
    Co-Authors: Gopal Pandurangan, Peter Robinson, Michele Scquizzato
    Abstract:

    This paper presents a randomized Las Vegas distributed algorithm that constructs a Minimum Spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in $\tilde{O}(D + \sqrt{n})$ time and exchanges $\tilde{O}(m)$ messages (both with high probability), where $n$ is the number of nodes of the network, $D$ is the diameter, and $m$ is the number of edges. This is the first distributed MST algorithm that matches \emph{simultaneously} the time lower bound of $\tilde{\Omega}(D + \sqrt{n})$ [Elkin, SIAM J. Comput. 2006] and the message lower bound of $\Omega(m)$ [Kutten et al., J.ACM 2015] (which both apply to randomized algorithms). The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower bound construction that shows one lower bound {\em does not} work for the other. To complement our algorithm, we present a new lower bound graph construction for which any distributed MST algorithm requires \emph{both} $\tilde{\Omega}(D + \sqrt{n})$ rounds and $\Omega(m)$ messages.

  • Energy-optimal distributed algorithms for Minimum Spanning Trees
    IEEE Journal on Selected Areas in Communications, 2009
    Co-Authors: Yongwook Choi, Maleq Khan, Gopal Pandurangan, V.s.a. Kumar
    Abstract:

    Traditionally, the performance of distributed algorithms has been measured in terms of time and message complexity.Message complexity concerns the number of messages transmitted over all the edges during the course of the algorithm. However, in energy-constrained ad hoc wireless networks (e.g., sensor networks), energy is a critical factor in measuring the efficiency of a distributed algorithm. Transmitting a message between two nodes has an associated cost (energy) and moreover this cost can depend on the two nodes (e.g., the distance between them among other things). Thus in addition to the time and message complexity, it is important to consider energy complexity that accounts for the total energy associated with the messages exchanged among the nodes in a distributed algorithm. This paper addresses the Minimum Spanning tree (MST) problem, a fundamental problem in distributed computing and communication networks. We study energy-efficient distributed algorithms for the Euclidean MST problem assuming random distribution of nodes. We show a non-trivial lower bound of Omega(log n) on the energy complexity of any distributed MST algorithm. We then give an energy-optimal distributed algorithm that constructs an optimal MST with energy complexity O(log n) on average and O(log n log log n) with high probability. This is an improvement over the previous best known bound on the average energy complexity of Omega(log2 n). Our energy-optimal algorithm exploits a novel property of the giant component of sparse random geometric graphs. All of the above results assume that nodes do not know their geometric coordinates. If the nodes know their own coordinates, then we give an algorithm with O(1) energy complexity (which is the best possible) that gives an O(1) approximation to the MST.

  • distributed algorithms for constructing approximate Minimum Spanning Trees in wireless sensor networks
    IEEE Transactions on Parallel and Distributed Systems, 2009
    Co-Authors: Maleq Khan, Gopal Pandurangan, V Anil S Kumar
    Abstract:

    While there are distributed algorithms for the MST problem, these algorithms require relatively large number of messages and time; this makes these algorithms impractical for resource-constrained networks such as ad hoc wireless sensor networks. In such networks, a sensor has very limited power, and any algorithm needs to be simple, local, and energy efficient for being practical. Motivated by these considerations, we design and analyze a class of simple and local distributed algorithms called nearest neighbor tree (NNT) algorithms for energy-efficient construction of MSTs in a wireless ad hoc setting. We assume that the nodes are uniformly distributed in a unit square and show provable bounds on the performance with respect to both the quality of the Spanning tree produced and the energy needed to construct them. In particular, we show that NNT produces a close approximation to the MST, and they can be maintained dynamically with polylogarithmic number of rearrangements under node insertions/deletions. We also perform extensive simulations of our algorithms. We tested our algorithms on both uniformly random distributions of nodes, and on a realistic distributions of nodes in an urban setting. Simulations validate the theoretical results and show that the bounds are much better in practice.

M R Henzinger - One of the best experts on this subject based on the ideXlab platform.

  • parametric and kinetic Minimum Spanning Trees
    Foundations of Computer Science, 1998
    Co-Authors: Pankaj K Agarwal, David Eppstein, Leonidas J Guibas, M R Henzinger
    Abstract:

    We consider the parametric Minimum Spanning tree problem, in which we are given a graph with edge weights that are linear functions of a parameter /spl lambda/ and wish to compute the sequence of Minimum Spanning Trees generated as /spl lambda/ varies. We also consider the kinetic Minimum Spanning tree problem, in which /spl lambda/ represents time and the graph is subject in addition to changes such as edge insertions, deletions, and modifications of the weight functions as time progresses. We solve both problems in time O(n/sup 2/3/log/sup 4/3/) per combinatorial change in the tree (or randomized O(n/sup 2/3/log/sup 4/3/ n) per change). Our time bounds reduce to O(n/sup 1/2/log/sup 3/2/ n) per change (O(n/sup 1/2/log n) randomized) for planar graphs or other minor-closed families of graphs, and O(n/sup 1/4/log/sup 3/2/ n) per change (O(n/sup 1/4/ log n) randomized) for planar graphs with weight changes but no insertions or deletions.

  • maintaining Minimum Spanning Trees in dynamic graphs
    International Colloquium on Automata Languages and Programming, 1997
    Co-Authors: M R Henzinger, Valerie King
    Abstract:

    We present the first fully dynamic algorithm for maintaining a Minimum Spanning tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. An immediate consequence is the first fully dynamic deterministic algorithm for maintaining connectivity and, bipartiteness in amortized time O(n 1/3 log n) per update, with O(1) worst case time per query.