Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations?
- $isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$
- $link(G,a,b)$: Adds an edge from $a$ to $b$ in the graph $G$
- $unlink(G,a,b)$: Removes the edge from $a$ to $b$ in $G$
- $add(G,a)$: Adds a vertex to G
- $remove(G,a)$: Removes a vertex from G
A few notes:
- If we disallowed $unlink$, it seems it would be easy to maintain the connectedness information, using a disjoint-set type data structure.
- Obviously, $isConnected$ could be implemented using depth or breadth-first search, using the naive pointer-based representation of the graph. But this is inefficient.
I'm hoping for amortized constant or logarithmic time for all three operations. Is this possible?
remove
also remove the incident edges? If so, requiring that operation to be O(log n) time might be too much to hope…. $\endgroup$ – Tsuyoshi Ito Feb 27 '11 at 0:15