An On-Line Edge-Deletion Problem
From MaRDI portal
Publication:3902517
DOI10.1145/322234.322235zbMath0454.68075OpenAlexW2085849292WikidataQ55891645 ScholiaQ55891645MaRDI QIDQ3902517
Publication date: 1981
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322234.322235
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Related Items
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Incomplete directed perfect phylogeny in linear time ⋮ Optimal on-line decremental connectivity in trees ⋮ Semi-dynamic shortest paths and breadth-first search in digraphs ⋮ Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs ⋮ Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning ⋮ Dynamic 2- and 3-connectivity on planar graphs ⋮ On the computational complexity of dynamic graph problems ⋮ Fast dynamic transitive closure with lookahead ⋮ Amortized efficiency of a path retrieval data structure ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition ⋮ Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs ⋮ A topological approach to dynamic graph connectivity ⋮ Finding paths and deleting edges in directed acyclic graphs ⋮ Maintaining minimum spanning trees in dynamic graphs ⋮ Least resolved trees for two-colored best match graphs ⋮ Decremental 2- and 3-connectivity on planar graphs ⋮ On dynamic shortest paths problems ⋮ Dynamic maintenance of directed hypergraphs ⋮ Building Cartesian trees from free trees with \(k\) leaves ⋮ Mantaining dynamic matrices for fully dynamic transitive closure ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ A special case the of dynamization problem for least cost paths ⋮ On-line computation of minimal and maximal length paths ⋮ Maintaining bridge-connected and biconnected components on-line ⋮ Incremental single-source shortest paths in digraphs with arbitrary positive arc weights ⋮ On Cartesian trees and range minimum queries ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An algorithm for strongly connected component analysis in \(n \log n\) symbolic steps ⋮ Fast compatibility testing for rooted phylogenetic trees ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ A fully dynamic algorithm for maintaining the transitive closure ⋮ Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs ⋮ Constructing Light Spanners Deterministically in Near-Linear Time ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study ⋮ Constructing light spanners deterministically in near-linear time ⋮ On-line computation of transitive closures of graphs ⋮ Semi-dynamic breadth-first search in digraphs ⋮ Dynamic cycle detection ⋮ Unnamed Item ⋮ Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time ⋮ Lifelong planning \(\text{A}^*\)
