Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
From MaRDI portal
Recommendations
- Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree
- An efficient parallel algorithm for updating minimum spanning trees
- Online minimum spanning tree with advice (extended abstract)
- scientific article; zbMATH DE number 177564
- Offline Algorithms for Dynamic Minimum Spanning Tree Problems
- scientific article; zbMATH DE number 4199627
- Incremental minimum spanning tree algorithms
Cited in
(82)- Dynamic mechanism design
- Shortest paths in linear time on minor-closed graph classes, with an application to Steiner tree approximation
- On-line updating of solutions to a class of matroid intersection problems
- Finding paths and deleting edges in directed acyclic graphs
- On-line computation of minimal and maximal length paths
- Maintaining bridge-connected and biconnected components on-line
- Forests, frames, and games: Algorithms for matroid sums and applications
- Finding the \(k\) smallest spanning trees
- Static and dynamic parallel computation of connected components
- A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
- Data structures for two-edge connectivity in planar graphs
- Dynamic Euclidean minimum spanning trees and extrema of binary functions
- Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
- Dyn-FO: A parallel, dynamic complexity class
- Divider-based algorithms for hierarchical tree partitioning.
- Optimal decremental connectivity in planar graphs
- Dynamic planar embeddings of dynamic graphs
- Dynamic path queries in linear space
- Fully dynamic biconnectivity in graphs
- Scheduling tree dags on parallel architectures
- Average case analysis of dynamic geometric optimization
- Decremental 2- and 3-connectivity on planar graphs
- An efficient algorithm for batch stability testing
- Fourier decompositions of graphs with symmetries and equitable partitions
- Multiple-edge-fault-tolerant approximate shortest-path trees
- Succinct indices for path minimum, with applications
- Optimal parallel algorithms for multiple updates of minimum spanning trees
- A uniform paradigm to succinctly encode various families of trees
- Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions
- Randomization for efficient dynamic graph algorithms (invited talk)
- Optimal on-line decremental connectivity in trees
- A survey on combinatorial optimization in dynamic environments
- Incremental network design with minimum spanning trees
- Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions
- Connectivity oracles for graphs subject to vertex failures
- Faster Fully-Dynamic Minimum Spanning Forest
- Maintenance of a minimum spanning forest in a dynamic plane graph
- scientific article; zbMATH DE number 177564 (Why is no real title available?)
- Offline Algorithms for Dynamic Minimum Spanning Tree Problems
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
- scientific article; zbMATH DE number 1471729 (Why is no real title available?)
- Minimizing diameters of dynamic trees
- Maintaining minimum spanning trees in dynamic graphs
- The saga of minimum spanning trees
- Maintaining spanning trees of small diameter
- Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
- Computing the map of geometric minimal cuts
- Single-source bottleneck path algorithm faster than sorting for sparse graphs
- Using sparsification for parametric minimum spanning tree problems
- Finding the k smallest spanning trees
- Dynamic 2- and 3-connectivity on planar graphs
- Fully dynamic 2-edge-connectivity in planar graphs
- A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
- Maintenance of triconnected components of graphs
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
- Updating Directed Minimum Cost Spanning Trees
- A consistent semantics of self-adjusting computation
- scientific article; zbMATH DE number 7651141 (Why is no real title available?)
- A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
- Online Minimum Spanning Tree with Advice
- Faster shortest-path algorithms for planar graphs
- Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
- Fully dynamic maintenance of vertex cover
- An algorithm for enumerating all directed spanning trees in a directed graph
- Fast algorithms via dynamic-oracle matroids
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- Complete equitable decompositions
- On partitioning minimum spanning trees
- Dynamic and static algorithms for optimal placement of resources in a tree
- Maintenance of 2- and 3-edge-connected components of graphs. I
- Fully dynamic strongly connected components in planar digraphs
- Maintaining \(\mathrm{CMSO}_2\) properties on dynamic structures with bounded feedback vertex number
- Good r-divisions imply optimal amortized decremental biconnectivity
- Fully-adaptive dynamic connectivity of square intersection graphs
- On maximal k-edge-connected subgraphs of undirected graphs
- Tree-packing revisited: faster fully dynamic min-cut and arboricity
- A note on set union with arbitrary deunions
- Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
- Dynamic maintenance of planar digraphs, with applications
- Maintaining dynamic minimum spanning trees: an experimental study
This page was built for publication: Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3694711)
