Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Take a blank page, draw some small circles, and connect them with a few arrows, and voilà you created a directed graph, a digraph for short. Now let us ask an algorithmic question: If I point out two of those circles to you, one as the start and one as the target, can you find a way to go from the start to the target by only using the arrows in their one-way direction? While this reachability question is well-studied, we found new algorithms for the following slight variations of the reachability problem: - What if we ask this questions for many starts and many targets while we also add and remove arrows in between answering these questions? - What if we want to find two ways from the start to the target that use completely different arrows? Or can we even find three disjoint paths? And how fast can we compute the answer for all combinations of starts and targets? For the dynamic reachability problem, we review the link-cut tree data structure for dynamic rooted forests before we extend it to a new class of dynamic graphs: partial-function graphs. We provide algorithms for arbitrarily interleaved queries and updates to the graph in time O(log n). In the generalized reachability problem, we ask about the existence of multiple arc-disjoint paths between the query vertices. The all-pairs k-reachability problem asks for the number of arc-disjoint paths between all vertex pairs, where one can answer 'at least k', whenever there are k or more arc-disjoint paths. 2-reachability answers basic resilience of paths, i.e., is there an arc that can not be avoided on the path from u to v. As our main result, we present an algorithm running in time O(n^ω log n) to compute all-pairs 2-reachability of any digraph, where ω is the matrix multiplication exponent. This result comes in three steps: first, we develop a path algebra with binary encodings for acyclic graphs, second, we use dominator trees to build auxiliary graphs that represent the answer for strongly connected graphs, and third, we carefully combine the two on ...