Reachability: Difference between revisions
m more specific stub type |
Corrected grammar: "notion of being able to" --> "ability to" |
||
Line 1: | Line 1: | ||
{{Citations missing|date=October 2009}} |
{{Citations missing|date=October 2009}} |
||
In [[graph theory]], '''reachability''' is the |
In [[graph theory]], '''reachability''' is the ability to get from one [[Vertex (graph theory)|vertex]] in a [[directed graph]] to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the [[connected components]] in the graph, which can be done in linear time. |
||
== Definition == |
== Definition == |
Revision as of 19:11, 15 January 2012
This article needs additional citations for verification. (October 2009) |
In graph theory, reachability is the ability to get from one vertex in a directed graph to some other vertex. Note that reachability in undirected graphs is trivial — it is sufficient to find the connected components in the graph, which can be done in linear time.
Definition
For a directed graph D = (V, A), the reachability relation of D is the transitive closure of its arc set A, which is to say the set of all ordered pairs (s, t) of vertices in V for which there exist vertices v0 = s, v1, …, vd = t such that (vi - 1, vi ) is in A for all 1 ≤ i ≤ d.
DAGs and partial orders
The reachability relation of a directed acyclic graph is a partial order; any partial order may be defined in this way, for instance as the reachability relation of its transitive reduction. If a directed graph is not acyclic, its reachability relation will be a preorder but not a partial order.
Algorithms
Algorithms for reachability fall into two classes: those that require preprocessing and those that do not. For the latter case, resolving a single reachability query can be done in linear time using algorithms such as breadth first search or iterative deepening depth-first search.
Typically algorithms for reachability that require preprocessing (and their corresponding data structures) are called oracles (similarly there are oracles for distance and approximate distance queries).
Node failures
A related problem is to solve reachability queries with some number k of node failures. For example: "Can node u still reach node v even though nodes s1, ..., sk have failed and can no longer be used?" The breadth-first search technique works just as well on such queries, but constructing an efficient oracle is more challenging.