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: 936
Venue: PODS
Year: 1991
Pagerank: 6.0220239e-05
Overall Rank: 5,975 | 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,491	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.3658999e-05
3,603	Overbound and Right-Linear Queries	1991	PODS	7.2683975e-05
8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.5028526e-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,330	Efficient Transitive Closure Algorithms	1988	VLDB	0.00011140171

Semantically Similar Papers

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