Skip to main content
fixed broken link to springerlink.com; added full citation in tooltip; added MathJax
Source Link

I have a problem that is reducible to (efficiently) determining the reachability of a node in a fully dynamic planar digraph.

I'm aware of "A fully dynamic data structure for reachability in planar digraphs""A fully dynamic data structure for reachability in planar digraphs" which provides O(n^(2/3) log n)$O(n^{2/3} \log n)$ query with a O(n)$O(n)$-space data structure.

Can this be / has this been bettered?

If all my queries have the same source node, is there a more efficient (in time/space/both) way?

Are there any other related literature that deals with more efficient queries albeit with more restrictions imposed on the digraph?

Thanks!

I have a problem that is reducible to (efficiently) determining the reachability of a node in a fully dynamic planar digraph.

I'm aware of "A fully dynamic data structure for reachability in planar digraphs" which provides O(n^(2/3) log n) query with a O(n)-space data structure.

Can this be / has this been bettered?

If all my queries have the same source node, is there a more efficient (in time/space/both) way?

Are there any other related literature that deals with more efficient queries albeit with more restrictions imposed on the digraph?

Thanks!

I have a problem that is reducible to (efficiently) determining the reachability of a node in a fully dynamic planar digraph.

I'm aware of "A fully dynamic data structure for reachability in planar digraphs" which provides $O(n^{2/3} \log n)$ query with a $O(n)$-space data structure.

Can this be / has this been bettered?

If all my queries have the same source node, is there a more efficient (in time/space/both) way?

Are there any other related literature that deals with more efficient queries albeit with more restrictions imposed on the digraph?

Thanks!

edited tags
Link
Suresh Venkat
  • 4.5k
  • 1
  • 26
  • 33
Source Link

Reachability in digraphs

I have a problem that is reducible to (efficiently) determining the reachability of a node in a fully dynamic planar digraph.

I'm aware of "A fully dynamic data structure for reachability in planar digraphs" which provides O(n^(2/3) log n) query with a O(n)-space data structure.

Can this be / has this been bettered?

If all my queries have the same source node, is there a more efficient (in time/space/both) way?

Are there any other related literature that deals with more efficient queries albeit with more restrictions imposed on the digraph?

Thanks!