Sparsification—a technique for speeding up dynamic graph algorithms
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 1256641
- scientific article; zbMATH DE number 1263228
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Separator-Based Sparsification II: Edge and Vertex Connectivity
- Separator based sparsification. I: Planarity testing and minimum spanning trees
Cited in
(72)- Reoptimization of minimum and maximum traveling salesman's tours
- Static and dynamic parallel computation of connected components
- Decomposable multi-parameter matroid optimization problems.
- Optimal decremental connectivity in planar graphs
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Linear time algorithms for two disjoint paths problems on directed acyclic graphs
- General compact labeling schemes for dynamic trees
- A fully dynamic graph algorithm for recognizing interval graphs
- An efficient algorithm for batch stability testing
- Constant-time dynamic weight approximation for minimum spanning forest
- Sparsification lower bound for linear spanners in directed graphs
- Multiple-edge-fault-tolerant approximate shortest-path trees
- Optimal per-edge processing times in the semi-streaming model
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- Incremental algorithm for maintaining a DFS tree for undirected graphs
- Algorithms for placing monitors in a flow network
- Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class
- Single-pass streaming algorithms to partition graphs into few forests
- Randomization for efficient dynamic graph algorithms (invited talk)
- Algorithms on evolving graphs
- A survey on combinatorial optimization in dynamic environments
- Speeding up Graph Algorithms via Switching Classes
- Incremental network design with minimum spanning trees
- Categorified Reeb graphs
- Connectivity oracles for graphs subject to vertex failures
- Mining preserving structures in a graph sequence
- Faster Fully-Dynamic Minimum Spanning Forest
- Compact separator decompositions in dynamic trees and applications to labeling schemes
- Efficient data structures for sparse network representation
- scientific article; zbMATH DE number 1256641 (Why is no real title available?)
- scientific article; zbMATH DE number 1471729 (Why is no real title available?)
- The saga of minimum spanning trees
- Configuring random graph models with fixed degree sequences
- Computing the map of geometric minimal cuts
- scientific article; zbMATH DE number 871915 (Why is no real title available?)
- Dynamic approximate vertex cover and maximum matching
- Local algorithms for bounded degree sparsifiers in sparse graphs
- Decremental SPQR-trees for Planar Graphs
- Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
- A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
- The online house numbering problem: min-max online list labeling
- The power of vertex sparsifiers in dynamic graph algorithms
- \(k\)-best solutions of MSO problems on tree-decomposable graphs
- An improved algorithm for incremental DFS tree in undirected graphs
- Determinant-preserving sparsification of SDDM matrices
- Fully dynamic spectral vertex sparsifiers and applications
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Fully dynamic maximal matching in O( n) update time
- A consistent semantics of self-adjusting computation
- Algorithmic aspects in speech recognition
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- scientific article; zbMATH DE number 7651196 (Why is no real title available?)
- Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
- Influence of assortativity and degree-preserving rewiring on the spectra of networks
- Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries
- Multi-priority graph sparsification
- Fast algorithms via dynamic-oracle matroids
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- On partitioning minimum spanning trees
- A formal verification technique for behavioural model-to-model transformations
- Supereulerian testing on semi-Eulerian graphs
- \(f\)-sensitivity distance oracles and routing schemes
- Vertex sparsifiers for hyperedge connectivity
- Good r-divisions imply optimal amortized decremental biconnectivity
- On maximal k-edge-connected subgraphs of undirected graphs
- Tree-packing revisited: faster fully dynamic min-cut and arboricity
- Incomplete directed perfect phylogeny in linear time
- Adjacency queries in dynamic sparse graphs
- Two methods for the generation of chordal graphs
- Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity
- Maintaining dynamic minimum spanning trees: an experimental study
- Fast reoptimization for the minimum spanning tree problem
This page was built for publication: Sparsification—a technique for speeding up dynamic graph algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4377592)
