Reachability: Difference between revisions
→Algorithms: Improved paragraph on preprocessing algorithms. |
m fixed link to "connected components" (it was going to a disambiguation page) |
||
| Line 1: | Line 1: | ||
{{Citations missing|date=October 2009}} |
{{Citations missing|date=October 2009}} |
||
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. |
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 component (graph theory)|connected components]] in the graph, which can be done in linear time. |
||
== Definition == |
== Definition == |
||
Revision as of 21:02, 15 August 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.
Preprocessing algorithms (such as a simplified Floyd–Warshall algorithm, or Thorup's algorithm for planar digraphs, which uses only O(n log n) time and space) create data structures which allow subsequent reachability queries to be answered in constant time (i.e., in a small fixed amount of time, independent of the size of the graph). Such algorithms (or their data structures) are sometimes called oracles, since the precomputed data structure allows any query to be answered immediately, similar to how Turing machine oracles answer questions. Many reachability algorithms (including the two mentioned above) can be easily extended to provide distance or approximate distance algorithms for graphs where each directed edge has a distance (usually called a weight).
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.
See also
.svg){kind=small} | This combinatorics-related article is a stub. You can help Wikipedia by expanding it. |