Mixed-Approach Algorithms for Transitive Closure

Summary: Analyzes two dual approaches for directed transitive closure that can differ asymptotically and combines them into a mixed reachability-tree algorithm. Proves a connectivity-based bound O(Σ_{(x,y)} CONN(x,y)) that better captures structural ease and outperforms many single-approach algorithms. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h2335c1bc56a6376c
Venue: PODS
Year: 1991
Pagerank: 5.8875106e-05
Overall Rank: 6,098 | 59.01%
DOI: 10.1145/113413.113431

Incoming Non-self Citations Over Time

Authors

1. Håkan Jakobsson (Stanford University)

BibTeX Citation

@inproceedings{jakobsson_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{Mixed-Approach Algorithms for Transitive Closure}},
        url = {https://dl.acm.org/doi/10.1145/113413.113431},
        doi = {10.1145/113413.113431},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Jakobsson, Håkan},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,555	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.2086693e-05
3,675	Overbound and Right-Linear Queries	1991	PODS	7.1075276e-05
8,195	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.3798301e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,363	Efficient Transitive Closure Algorithms	1988	VLDB	0.00010914322

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,140	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB
2	11,540	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD
3	3,555	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD
4	5,150	Minimum Spanning Trees in Temporal Graphs	2015	SIGMOD
5	1,287	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB
6	1,329	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD
7	6,981	Hybrid Transitive Closure Algorithms	1990	VLDB
8	8,195	On Tree-Based Techniques for Query Evaluation	1992	PODS
9	1,904	The Input/Output Complexity Of Transitive Closure	1990	SIGMOD
10	1,363	Efficient Transitive Closure Algorithms	1988	VLDB