|
Tri-College DSpace Repository >
HAVERFORD COLLEGE >
Student Scholarship >
Senior Theses >
Computer Science >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10066/3754
|
| Title: | An Explication of "A New Algorithm for Transitive Closures and Computation of Recursion in Relational Databases" by Yangjun Chen |
| Author(s): | Miller, Anne |
| Department: | Haverford College. Dept. of Computer Science |
| Issue Date: | 2008 |
| Abstract: | In this paper, we discuss the algorithm for computing the transitive closure of a directed, acyclic graph of bounded degree given in Yangjun Chen’s paper, "A New Algorithm for Transitive Closures and Computation of Recursion in Relational Databases" [2]. We point out several errors, one in the correctness of the algorithm and one in the complexity, and modify the algorithm slightly to repair the former. (The error in complexity does not seem to be as easily fixable.) We then prove the correctness of the altered algorithm. |
| URL: | http://hdl.handle.net/10066/3754 |
| Appears in Collections: | Computer Science
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|
