Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

8
votes
2answers
165 views

Computing a transitive completion / path existance oracle

There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible: Assume we get an input directed graph $G$ and would like to answer ...
9
votes
5answers
529 views

Transitivity check vs. Transitive Closure

Is checking transitivity of a digraph not easier than (in terms of asymptotic complexity) taking the transitive closure of the digraph? Do we know any lower bound better than $\Omega(n^2)$ to ...
6
votes
0answers
200 views

Restricted Reachability Problem

Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges. Choose some subset of $n\leq V$ "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we ...
7
votes
1answer
482 views

Approximating transitive reduction of a transitive closure of a dag

Let's suppose a transitive closure $G^+$ of a dag $G$ is given and we want to compute an approximation of the transitive reduction $G^-$ such that the full transitive reduction is a subgraph of the ...
12
votes
1answer
557 views

Online transitive closure better than O(N^2) per edge addition

I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this: ...