Theoretical Computer Science Asked by wei wang on November 16, 2020
Consider the standard s-t reachability problem of finding a path between nodes $s$ and $t$ in a directed graph $G$. A DFS or BFS could solve it.
Would it be possible to pre-process the graph and compute some “hints” among all nodes in the graph, such that given any node pair $s$ and $t$, the DFS or BFS procedure knows that some edges are more likely contributing to a path (if any) between $s$ and $t$? Therefore, the DFS or BFS will only traverse the “promising” edges to find the $s$–$t$ path. Is it a known problem?
Transitive closure could be one possible “hint”. I am wondering if there is any cheaper solution, preferably in O(n) time.
Edits: “promising” means very likely. It appears that it’s difficult to compute definitive promising edges (i.e., the edges will definitely be in an $s$–$t$ path). However, will it be possible to compute the promising edges by allowing some reasonable error?
The Reachability Wikipedia page lists several solutions, although the only one which works for general graphs involves computing the transitive closure, which it sounds like you want to avoid. This is additionally for exact computations of the path.
Answered by Mark on November 16, 2020
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP