Sparsification—a technique for speeding up dynamic graph algorithms
From MaRDI portal
Publication:4377592
DOI10.1145/265910.265914zbMath0891.68072OpenAlexW2009695707WikidataQ56031168 ScholiaQ56031168MaRDI QIDQ4377592
Giuseppe F. Italiano, A. Nissenzweig, David Eppstein, Zvi Galil
Publication date: 17 February 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1997-44/
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items
Incomplete directed perfect phylogeny in linear time, Faster Fully-Dynamic Minimum Spanning Forest, Categorified Reeb graphs, Optimal per-edge processing times in the semi-streaming model, A survey on combinatorial optimization in dynamic environments, Mining preserving structures in a graph sequence, Compact separator decompositions in dynamic trees and applications to labeling schemes, Sparsification upper and lower bounds for graph problems and not-all-equal SAT, Incremental algorithm for maintaining a DFS tree for undirected graphs, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case, Influence of assortativity and degree-preserving rewiring on the spectra of networks, Decomposable multi-parameter matroid optimization problems., Optimal decremental connectivity in planar graphs, Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions, Unnamed Item, Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries, Determinant-Preserving Sparsification of SDDM Matrices, Single-pass streaming algorithms to partition graphs into few forests, Incremental Network Design with Minimum Spanning Trees, General compact labeling schemes for dynamic trees, Algorithms for placing monitors in a flow network, A fully dynamic graph algorithm for recognizing interval graphs, Unnamed Item, An efficient algorithm for batch stability testing, The saga of minimum spanning trees, Computing the map of geometric minimal cuts, Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class, Two methods for the generation of chordal graphs, A consistent semantics of self-adjusting computation, Decremental SPQR-trees for Planar Graphs, Configuring Random Graph Models with Fixed Degree Sequences, A formal verification technique for behavioural model-to-model transformations, \(f\)-sensitivity distance oracles and routing schemes, Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity, Maintaining dynamic minimum spanning trees: an experimental study, Dynamic Approximate Vertex Cover and Maximum Matching, Fast reoptimization for the minimum spanning tree problem, Unnamed Item, Randomization for Efficient Dynamic Graph Algorithms, Unnamed Item, Unnamed Item, Constant-time dynamic weight approximation for minimum spanning forest, Connectivity Oracles for Graphs Subject to Vertex Failures, Sparsification lower bound for linear spanners in directed graphs, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier, Multiple-edge-fault-tolerant approximate shortest-path trees, The Online House Numbering Problem: Min-Max Online List Labeling, Reoptimization of minimum and maximum traveling salesman's tours, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time, Unnamed Item, Static and dynamic parallel computation of connected components
