Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs

DOI10.1007/978-3-662-47672-7_59zbMath1427.68244arXiv1612.03856OpenAlexW653534090MaRDI QIDQ3448830

Danupon Nanongkai, Sebastian Krinninger, Monika R. Henzinger

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

Unnamed Item ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time

Cites Work

• Unnamed Item
• Finding paths and deleting edges in directed acyclic graphs
• Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
• Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
• High-Probability Parallel Transitive-Closure Algorithms
• Improved Dynamic Reachability Algorithms for Directed Graphs
• An On-Line Edge-Deletion Problem
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
• Decremental maintenance of strongly connected components

This page was built for publication: Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs