GRAPH REACHABILITY QURIES : A SURVEY


Advisor : Prof. Kun-Ta,Chuang
Student : Yi-Wei,Wang

Time/Space Complexity of different approaches

Directed graph to DAG

Tree + SSPI

PL(b1)={c2, a1}, both of which are immediate surplus predecessors of b1.
While a1 is a surrogate predecessor for both e2 and m2.

Dual-labeling

Link table : 9→[6,9) , 7→[1,5)

Bipartite Matching

Re-labeling a subgraph

Reserving all alternative paths