DBScholar

Back to papers

DAG Reduction: Fast Answering Reachability Queries

Summary: Proposes DAG reduction to accelerate reachability queries by shrinking DAGs with transitive reduction (TR) and equivalence reduction (ER). buTR yields the smallest DAG with the same transitive closure; linear-ER compresses further in linear time for scalable reachability on large graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
5355
Venue
SIGMOD
Year
2017
Pagerank
5.5636745e-05
Overall Rank
7,707 | 47.13%
DOI
10.1145/3035918.3035927

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{zhou_sigmod17,
        title = {{DAG Reduction: Fast Answering Reachability Queries}},
        author = {Zhou, Junfeng and Zhou, Shijie and Yu, Jeffrey Xu and Wei, Hao and Chen, Ziyang and Tang, Xian},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3035927},
        url = {https://dl.acm.org/doi/10.1145/3035918.3035927},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank Citing Paper Year Venue Pagerank
927 Real-time Constrained Cycle Detection in Large Dynamic Graphs 2018 VLDB 0.00013161079
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Previous Page 1 / 1 Next

Semantically Similar Papers