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
hecfffcfe3bab218f
Venue
SIGMOD
Year
2017
Pagerank
5.442834e-05
Overall Rank
7,840 | 47.29%
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
937 Real-time Constrained Cycle Detection in Large Dynamic Graphs 2018 VLDB 0.00012977594
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