scientific article; zbMATH DE number 7238971

DOI10.4230/LIPIcs.SWAT.2018.16zbMath1477.05178arXiv1607.04913MaRDI QIDQ5116480

Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang

Publication date: 25 August 2020

Full work available at URL: https://arxiv.org/abs/1607.04913

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

fractional cascadingfully dynamic algorithmDFS tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (7)

Fault tolerant depth first search in undirected graphs: simple yet efficient ⋮ Unnamed Item ⋮ Sublinear-time reductions for big data computing ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ Space-efficient fully dynamic DFS in undirected graphs ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Sublinear-time reductions for big data computing

Cites Work

• Unnamed Item
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs
• Fractional cascading. I: A data structuring technique
• Fractional cascading. II: Applications
• Sorted Range Reporting
• Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs
• On Dynamic DFS Tree in Directed Graphs
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Sparsification—a technique for speeding up dynamic graph algorithms
• Dynamic DFS in Undirected Graphs: breaking the O(m) barrier
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• Fully-dynamic min-cut
• A new approach to dynamic all pairs shortest paths
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Fully Dynamic Maximal Matching in O (log n) Update Time
• Depth-First Search and Linear Graph Algorithms
• Dynamic graph connectivity in polylogarithmic worst case time

This page was built for publication: