On the shortest path and minimum spanning tree problems
| dc.contributor.advisor | Ramachandran, Vijaya | en |
| dc.creator | Pettie, Seth | en |
| dc.date.accessioned | 2008-08-28T21:37:15Z | en |
| dc.date.available | 2008-08-28T21:37:15Z | en |
| dc.date.issued | 2003 | en |
| dc.description | text | en |
| dc.description.abstract | The shortest path and minimum spanning tree problems are two of the classic textbook problems in combinatorial optimization. They are simple to describe and admit simple polynomial-time algorithms. However, despite years of concerted research effort, the asymptotic complexity of these problems remains unresolved. The main contributions of this dissertation are a number of asymptotically faster algorithms for the minimum spanning tree and shortest path problems. Of equal interest, we provide some clues as to why these problems are so diffcult. In particular, we show why certain modern approaches to the problems are doomed to have super-linear complexity. A sampling of our results are listed below. We emphasize that all of our algorithms work with general graphs, and make no restrictive assumptions on the numerical representation of edge-lengths. A provably optimal deterministic minimum spanning tree algorithm. (We give a constructive proof that the algorithmic complexity of the minimum spanning tree problem is equivalent to its decision-tree complexity.) An all-pairs shortest path algorithm for general graphs running in time O(mn + n2 log log n), where m and n are the number of edges and vertices. This provides the first improvement over approaches based on Dijkstra's algorithm. An all-pairs shortest path algorithm for undirected graphs running in O(mn log α ) time, where α = α (m, n) is the inverse-Ackermann function. A single-source shortest path algorithm running in O(m α +min{n log log r, n log n}) time, where r bounds the ratio of any two edge lengths. For r polynomial in n this is O(m + n log log n), an improvement over Dijkstra's algorithm. An inverse-Ackermann style lower bound for the online minimum spanning tree veri cation problem. This is the rst inverse-Ackermann type lower bound for a comparison-based problem. An Ω (m + n log n) lower bound on any hierarchy-type single-source shortest path algorithm, implying that this type of algorithm cannot improve upon Dijkstra's algorithm. (All of our shortest path algorithms are of the hierarchy type.) The first parallel minimum spanning tree algorithm that is optimal w.r.t. to both time and work. Our algorithm is for the EREW PRAM model. A parallel, expected linear-work minimum spanning tree algorithm using only a polylogarithmic number of random bits. An O(mn log α ) bound on the comparison-addition complexity of all-pairs shortest paths. This is within a tiny log α factor of optimal when m = O(n). | |
| dc.description.department | Computer Science | |
| dc.format.medium | electronic | en |
| dc.identifier | b57185980 | en |
| dc.identifier.oclc | 56889714 | en |
| dc.identifier.proqst | 3118057 | en |
| dc.identifier.uri | http://hdl.handle.net/2152/859 | en |
| dc.language.iso | eng | en |
| dc.rights | Copyright is held by the author. Presentation of this material on the Libraries' web site by University Libraries, The University of Texas at Austin was made possible under a limited license grant from the author who has retained all copyrights in the works. | en |
| dc.subject.lcsh | Spanning trees (Graph theory) | en |
| dc.subject.lcsh | Paths and cycles (Graph theory) | en |
| dc.subject.lcsh | Combinatorial optimization | en |
| dc.title | On the shortest path and minimum spanning tree problems | en |
| dc.type.genre | Thesis | en |
| thesis.degree.department | Computer Sciences | en |
| thesis.degree.discipline | Computer Sciences | en |
| thesis.degree.grantor | The University of Texas at Austin | en |
| thesis.degree.level | Doctoral | en |
| thesis.degree.name | Doctor of Philosophy | en |