As the title. The incremental algorithm maintains the reachability information  of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if node u reaches node v) time.It takes amortized O(n) time for each edge insertion (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(23):273281, 1986.) on general directed graphs. Is it possible to do it faster on DAGs?
What is the fastest deterministic algorithm for incremental DAG reachability?
graph theory;graph algorithms;dynamic algorithms