Recent advances in fully dynamic graph algorithms (invited talk)
From MaRDI portal
Cites work
- (1 + )-approximate incremental matching in constant deterministic amortized time
- A deamortization approach for dynamic spanner and dynamic maximal matching
- A dynamic topological sort algorithm for directed acyclic graphs
- A faster and simpler fully dynamic transitive closure
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- A new approach to dynamic all pairs shortest paths
- A new approach to the maximum-flow problem
- A new deterministic algorithm for dynamic set cover
- A note on two problems in connexion with graphs
- Algorithm Theory - SWAT 2004
- Algorithmic aspects in speech recognition
- Algorithms and hardness for diameter in dynamic graphs
- Algorithms for computational biology. Second international conference, AlCoB 2015, Mexico City, Mexico, August 4--5, 2015. Proceedings
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
- An efficient generator for clustered dynamic random networks
- An experimental study of algorithms for fully dynamic transitive closure
- An experimental study of dynamic algorithms for transitive closure
- An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms
- An improved diffusion algorithm for dynamic load balancing.
- An Incremental Algorithm for a Generalization of the Shortest-Path Problem
- An incremental algorithm for the maximum flow problem
- An On-Line Edge-Deletion Problem
- Approximating Betweenness Centrality in Fully Dynamic Networks
- Approximating betweenness centrality in large evolving networks
- Approximating minimum cuts under insertions
- Arc-flags in dynamic graphs
- Batch-parallel Euler tour trees
- Betweenness centrality -- incremental and faster
- Combining hierarchical and goal-directed speed-up techniques for Dijkstra's algorithm
- Complexity models for incremental computation
- Computer vision. Detection, recognition and reconstruction. Selected papers based on the presentations at the international computer vision summer school -- ICVSS.
- Computing and Combinatorics
- Computing and Combinatorics
- Computing the shortest path: A^ search meets graph theory
- Computing Top-k Closeness Centrality in Fully-dynamic Graphs
- Counting Triangles under Updates in Worst-Case Optimal Time
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Deterministic dynamic matching in \(O(1)\) update time
- Deterministic fully dynamic data structures for vertex cover and matching
- Deterministic fully dynamic data structures for vertex cover and matching
- Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
- Dynamic algorithms via the primal-dual method
- Dynamic approximate all-pairs shortest paths in undirected graphs
- Dynamic approximate shortest paths and beyond: subquadratic and worst-case update time
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Dynamic graph clustering combining modularity and smoothness
- Dynamic graph clustering using minimum-cut trees
- Dynamic graph connectivity in polylogarithmic worst case time
- Dynamic load balancing by diffusion in heterogeneous systems
- Dynamic maintenance of a shortest-path tree on homogeneous batches of updates: new algorithms and experiments
- Dynamic Matching Algorithms in Practice
- Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms
- Dynamic matrix inverse: improved algorithms and matching conditional lower bounds
- Dynamic set cover: improved algorithms and lower bounds
- Dynamic transitive closure via dynamic matrix inverse (extended abstract)
- Dynamic trees in practice
- Efficient algorithms for updating betweenness centrality in fully dynamic graphs
- Experimental algorithms. 10th international symposium, SEA 2011, Kolimpari, Chania, Crete, Greece, May 5--7, 2011. Proceedings
- Experimental algorithms. 6th international workshop, WEA 2007, Rome, Italy, June 6--8, 2007. Proceedings.
- Experimental algorithms. 8th international symposium, SEA 2009, Dortmund, Germany, June 4--6, 2009. Proceedings
- Experimental analysis of dynamic all pairs shortest path algorithms
- Extended dynamic subgraph statistics using h-index parameterized data structures
- Fast dynamic cuts, distances and effective resistances via vertex sparsifiers
- Faster and more dynamic maximum flow by incremental breadth-first search
- Faster dynamic matchings and vertex connectivity
- Faster fully dynamic matchings with small approximation ratios
- Faster fully dynamic transitive closure in practice
- Faster Fully-Dynamic Minimum Spanning Forest
- Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
- Fully Dynamic 2-Hop Cover Labeling
- Fully dynamic (1+ e)-approximate matchings
- Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs
- Fully dynamic all-pairs shortest paths with worst-case update-time revisited
- Fully dynamic all-pairs shortest paths: breaking the O(n) barrier
- Fully dynamic almost-maximal matching: breaking the polynomial worst-case time barrier
- Fully dynamic betweenness centrality
- Fully dynamic biconnectivity in graphs
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Fully dynamic maintenance of vertex cover
- Fully dynamic maximal independent set in expected poly-log update time
- Fully dynamic maximal independent set with polylogarithmic update time
- Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
- Fully dynamic maximal independent set with sublinear update time
- Fully dynamic maximal matching in O( n) update time
- Fully dynamic maximal matching in constant update time
- Fully Dynamic Single-Source Reachability in Practice: An Experimental Study
- Fully dynamic update of arc-flags
- Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
- Fully-dynamic approximation of betweenness centrality
- Fully-dynamic hierarchical graph clustering using cut trees
- Fully-dynamic min-cut
- Geometric containers for efficient shortest-path computation
- scientific article; zbMATH DE number 1617242 (Why is no real title available?)
- scientific article; zbMATH DE number 432748 (Why is no real title available?)
- scientific article; zbMATH DE number 1263228 (Why is no real title available?)
- scientific article; zbMATH DE number 1956218 (Why is no real title available?)
- scientific article; zbMATH DE number 1775391 (Why is no real title available?)
- scientific article; zbMATH DE number 1798166 (Why is no real title available?)
- scientific article; zbMATH DE number 6866348 (Why is no real title available?)
- scientific article; zbMATH DE number 1926664 (Why is no real title available?)
- scientific article; zbMATH DE number 871917 (Why is no real title available?)
- scientific article; zbMATH DE number 6472606 (Why is no real title available?)
- scientific article; zbMATH DE number 7651141 (Why is no real title available?)
- scientific article; zbMATH DE number 7651158 (Why is no real title available?)
- Improved Data Structures for Fully Dynamic Biconnectivity
- Improved streaming algorithms for weighted matching, via unweighted matching
- Incremental exact min-cut in polylogarithmic amortized update time
- Logarithmic Lower Bounds in the Cell-Probe Model
- Lower bounds for fully dynamic connectivity problems in graphs
- Maintaining a large matching and a small vertex cover
- Maintaining a topological order under edge insertions
- Maintaining approximate maximum weighted matching in fully dynamic graphs
- Maintaining dynamic minimum spanning trees: an experimental study
- Maintaining minimum spanning trees in dynamic graphs
- Max flows in O(nm) time, or better
- New deterministic approximation algorithms for fully dynamic matching
- On a routing problem
- On dynamic shortest paths problems
- On the computational complexity of dynamic graph problems
- Parallel static and dynamic multi‐constraint graph partitioning
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Popular conjectures as a barrier for dynamic planar graph algorithms
- Popular conjectures imply strong lower bounds for dynamic problems
- Power balance and apportionment algorithms for the United States Congress
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Scalable Katz Ranking Computation in Large Static and Dynamic Graphs
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Separator-Based Sparsification II: Edge and Vertex Connectivity
- Shortest Path Tree Computation in Dynamic Graphs
- Simple deterministic algorithms for fully dynamic maximal matching
- Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
- Space-efficient fully dynamic DFS in undirected graphs
- Speeding up dynamic shortest-path algorithms
- The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
- The State of the Art in Dynamic Graph Algorithms
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Towards optimal dynamic indexes for approximate (and exact) triangle counting
- Towards polynomial lower bounds for dynamic problems
- Triangle counting in dynamic graph streams
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Worst-case update times for fully-dynamic all-pairs shortest paths
This page was built for publication: Recent advances in fully dynamic graph algorithms (invited talk)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7395537)
