Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
From MaRDI portal
Publication:3694711
DOI10.1137/0214055zbMath0575.68068OpenAlexW2121473031MaRDI QIDQ3694711
Publication date: 1985
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1367&context=cstech
Related Items
Succinct indices for path minimum, with applications ⋮ A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges ⋮ Data structures for two-edge connectivity in planar graphs ⋮ Optimal parallel algorithms for multiple updates of minimum spanning trees ⋮ Maintaining spanning trees of small diameter ⋮ Optimal on-line decremental connectivity in trees ⋮ On-line updating of solutions to a class of matroid intersection problems ⋮ Faster Fully-Dynamic Minimum Spanning Forest ⋮ Dynamic Euclidean minimum spanning trees and extrema of binary functions ⋮ Using sparsification for parametric minimum spanning tree problems ⋮ Fully dynamic biconnectivity in graphs ⋮ Finding the k smallest spanning trees ⋮ Dynamic 2- and 3-connectivity on planar graphs ⋮ Fully dynamic 2-edge-connectivity in planar graphs ⋮ A survey on combinatorial optimization in dynamic environments ⋮ A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs ⋮ A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions ⋮ Scheduling tree dags on parallel architectures ⋮ Finding paths and deleting edges in directed acyclic graphs ⋮ Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm ⋮ Average case analysis of dynamic geometric optimization ⋮ Dyn-FO: A parallel, dynamic complexity class ⋮ Minimizing diameters of dynamic trees ⋮ Maintaining minimum spanning trees in dynamic graphs ⋮ Decremental 2- and 3-connectivity on planar graphs ⋮ Certificates and fast algorithms for biconnectivity in fully-dynamic graphs ⋮ Optimal decremental connectivity in planar graphs ⋮ Dynamic planar embeddings of dynamic graphs ⋮ Unnamed Item ⋮ Fully dynamic maintenance of vertex cover ⋮ Incremental Network Design with Minimum Spanning Trees ⋮ Dynamic maintenance of planar digraphs, with applications ⋮ A uniform paradigm to succinctly encode various families of trees ⋮ Unnamed Item ⋮ An efficient algorithm for batch stability testing ⋮ The saga of minimum spanning trees ⋮ Divider-based algorithms for hierarchical tree partitioning. ⋮ Computing the map of geometric minimal cuts ⋮ Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs. ⋮ On-line computation of minimal and maximal length paths ⋮ A consistent semantics of self-adjusting computation ⋮ Maintaining bridge-connected and biconnected components on-line ⋮ Forests, frames, and games: Algorithms for matroid sums and applications ⋮ Dynamic and static algorithms for optimal placement of resources in a tree ⋮ Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time ⋮ Finding the \(k\) smallest spanning trees ⋮ Maintenance of 2- and 3-edge-connected components of graphs. I ⋮ Maintaining dynamic minimum spanning trees: an experimental study ⋮ Faster shortest-path algorithms for planar graphs ⋮ Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ Maintenance of triconnected components of graphs ⋮ Dynamic path queries in linear space ⋮ Fourier decompositions of graphs with symmetries and equitable partitions ⋮ Dynamic mechanism design ⋮ A note on set union with arbitrary deunions ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Multiple-edge-fault-tolerant approximate shortest-path trees ⋮ Static and dynamic parallel computation of connected components ⋮ A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
