Streaming Complexity of Spanning Tree Computation. The semistreaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an nnode input graph to be read sequentially in p passes using tildeO(n) space. In this model, some graph problems, such as spanning trees and kconnectivity, can be exactly solved in a single pass; while other graph problems, such as triangle detection and unweighted allpairs shortest paths, are known to require tildeOmega(n) passes to compute. For many fundamental graph problems, the tractability in these models is open. In this paper, we study the tractability of computing some standard spanning trees. Our results are:  :106,MaximumLeaf Spanning Trees. This problem is known to be APXcomplete with inapproximability constant rhoin245244,2). By constructing an varepsilonMLST sparsifier, we show that for every constant varepsilon u003e 0, MLST can be approximated in a single pass to within a factor of 1varepsilon w.h.p. (albeit in superpolynomial time for varepsilon le rho1 assuming mathrmP ne mathrmNP).  :162,BFS Trees. It is known that :162,BFS trees require omega(1) passes to compute, but the naive approach needs O(n) passes. We devise a new randomized algorithm that reduces the pass complexity to O(sqrtn), and it offers a smooth tradeoff between pass complexity and space usage.  :208,DFS Trees. The current best algorithm by Khan and Mehta STACS 2019 takes tildeO(h) passes, where h is the height of computed :208,DFS trees. Our contribution is twofold. First, we provide a simple alternative proof of this result, via a new connection to sparse certificates for knodeconnectivity. Second, we present a randomized algorithm that reduces the pass complexity to O(sqrtn), and it also offers a smooth tradeoff between pass complexity and space usage.

A Supernodal AllPairs Shortest Path Algorithm We show how to exploit graph sparsity in the FW algorithm for the allpairs shortest path (APSP) problem. FW is an attractive choice for APSP on highperforming systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, FW will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between FW and Gaussian elimination, and thereby import several algorithmic techniques from sparse Cholesky factorization, namely, fillin reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality, and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than a baseline FW that does not exploit sparsity. Our experiments suggest that FW algorithm can be competitive with Dijkstraxe2x80x99s algorithm (the algorithmic core of Johnsonxe2x80x99s algorithm) for several classes sparse graphs.Npiyush kumar saoOak Ridge National LabRamki KannanOak Ridge National LaboratoryPras