Back to Seth Pettie's Hompage
Ph.D. Thesis
@PhDThesis{Pet-thesis,
author = "Seth Pettie",
title = "On the Shortest Path and Minimum Spanning Tree Problems",
school = "The University of Texas at Austin",
year = "2003",
type = "{P}h.{D}. Thesis",
note = "Department of Computer Sciences Technical Report TR-03-35,
http://www.cs.utexas.edu/ftp/pub/techreports/tr03-35.ps.gz",
month = "August",
}
Journal Articles
@article{PetRam-RandMST,
author = {S. Pettie and V. Ramachandran},
title = {Randomized Minimum Spanning Tree Algorithms Using Exponentially
Fewer Random Bits},
journal = {ACM Transactions on Algorithms},
volume = {4},
number = {1},
year = {2008},
pages = {1--27},
}
@article{PetUndirectedSP,
author = {S. Pettie and V. Ramachandran},
title = {A Shortest Path Algorithm for Real-Weighted
Undirected Graphs},
journal = SICOMP,
volume = {34},
number = {6},
year = {2005},
pages = {1398--1431},
}
@article{PetInvAck,
author = {Seth Pettie},
title = {An Inverse-{A}ckermann Type Lower Bound for Online
Minimum Spanning Tree Verification},
journal = {Combinatorica},
volume = {26},
number = {2},
pages = {207--230},
year = {2006},
}
@article{PS04,
author = {Seth Pettie and Peter Sanders},
title = {A simpler linear time $2/3 - \epsilon$ Approximation
to Maximum Weight Matching},
journal = {Information Processing Letters},
volume = {91},
number = {6},
pages = {271--276},
year = {2004},
}
@article{Pet03,
author = {Seth Pettie},
title = {A New Approach to All-Pairs Shortest Paths on
Real-Weighted Graphs},
journal = {Theoretical Computer Science},
volume = {312},
number = {1},
pages = {47--74},
year = {2003},
note = {special issue of selected papers from ICALP 2002},
}
@article{PR02c,
author = {Seth Pettie and Vijaya Ramachandran},
title= {An optimal minimum spanning tree algorithm},
journal = {J. {ACM}},
volume = {49},
number = {1},
year = {2002},
pages = {16--34},
}
@article{PR02d,
author = {Seth Pettie and Vijaya Ramachandran},
title = {A randomized time-work optimal parallel algorithm for
finding a minimum spanning forest},
journal = {SIAM J. Comput.},
volume = {31},
number = {6},
year = {2002},
pages = {1879--1895},
}
Conference Papers
@inproceedings{Pettie-Spanner-08,
author = {S. Pettie},
title = {Distributed Algorithms for Ultrasparse Spanners and Linear Size
Skeletons},
booktitle = {Proc. 27th ACM Symposium on Principles of Distributed Computing},
year = {2008},
pages = {},
}
@inproceedings{LotkerPP-08,
author = {Z. Lotker and B. Patt-Shamir and S. Pettie},
title = {Improved Distributed Approximate Matching},
booktitle = {Proc. 20th ACM Symposium on Parallel Algorithms and
Architectures},
year = {2008},
pages = {},
}
@inproceedings{DuanPettie08,
author = {R. Duan and S. Pettie},
title = {Bounded-leg Distance and Reachability Oracles},
booktitle = {Proc. 19th {ACM}-{SIAM} Symposium on Discrete Algorithms},
year = {2008},
pages = {436--445},
}
@inproceedings{Pettie-Deque-08,
author = {S. Pettie},
title = {Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture},
booktitle = {Proc. 19th {ACM}-{SIAM} Symposium on Discrete Algorithms},
year = {2008},
pages = {1115--1124},
}
@inproceedings{Pettie-Spanner-07,
author = {S. Pettie},
title = {Low Distortion Spanners},
booktitle = {Proc. 34th Int'l Colloq. on
Automata, Languages, and Programming ({ICALP})},
year = {2007},
pages = {78--87},
}
@inproceedings{Pettie-Sensitivity-05,
author = {S. Pettie},
title = {Sensitivity Analysis of Minimum Spanning Trees
in Sub-Inverse-{A}ckermann Time},
pages = {964--973},
year = {2005},
booktitle = {Proceedings 16th Int'l Symposium on Algorithms
and Computation ({ISAAC})},
}
@inproceedings{Pettie05,
author = {S. Pettie},
title = {Towards a Final Analysis of Pairing Heaps},
pages = {174--183},
year = {2005},
booktitle = {Proceedings 46th Annual Symposium on Foundations of
Computer Science ({FOCS})},
}
@inproceedings{MortensenPettie05,
author = {C.~W. Mortensen and S. Pettie},
title = {The Complexity of Implicit and
Space-Efficient Priority Queues},
pages = {49--60},
year = {2005},
booktitle = {Proceedings 9th Biennial Workshop on Algorithms
and Data Structures ({WADS})},
}
@inproceedings{BTMP05,
author = {Surender Baswana and Telikepalli Kavitha
and Kurt Mehlhorn and Seth Pettie},
title = {New constructions of $(\alpha,\beta)$-spanners
and purely additive spanners},
year = {2005},
booktitle = {Proc.~16th Ann.~{ACM}-{SIAM} Symposium on
Discrete Algorithms ({SODA})},
pages = {672--681},
}
@inproceedings{Pet02b,
author = "Seth Pettie",
title = "On the Comparison-Addition Complexity of All-Pairs
Shortest Paths",
year = "2002",
pages = "32--43",
booktitle = "Proc. 13th Annual Int'l Symp. on Algorithms and
Computation ({ISAAC})",
}
@inproceedings{Pet02a,
author = "Seth Pettie",
title = "An Inverse-{Ackermann} Style Lower Bound for the Online
Minimum Spanning Tree Verification Problem",
year = "2002",
pages = "155--163",
booktitle = "Proc. 43rd Annual Symposium on Foundations of
Computer Science ({FOCS})",
}
@inproceedings{Pet02,
author = "S. Pettie",
title = "A Faster All-pairs Shortest Path Algorithm
for Real-weighted Sparse Graphs",
booktitle = "Proceedings of 29th International Colloquium on
Automata, Languages, and Programming ({ICALP}),
{LNCS} Vol. 2380",
pages = "85--97",
year = "2002",
}
@inproceedings{GP02,
author = "H. Gabow and S. Pettie",
title = "The Dynamic Vertex Minimum Problem and Its Application
to Clustering-type Approximation Algorithms",
booktitle = "Proceedings 8th Scandinavian Workshop on Algorithm
Theory ({SWAT}), {LNCS} Vol. 2368",
pages = "190--199",
year = "2002",
}
@InProceedings{PR02b,
author = "S. Pettie and V. Ramachandran",
title = "Minimizing randomness in minimum spanning tree,
parallel connectivity and set maxima algorithms",
booktitle = "Proceedings of the 13th Annual {ACM}-{SIAM} Symposium
on Discrete Algorithms ({SODA})",
pages = "713--722",
year = "2002",
}
@InProceedings{PR02a,
author = "S. Pettie and V. Ramachandran",
title = "Computing shortest paths with comparisons and additions",
booktitle = "Proceedings of the 13th Annual {ACM}-{SIAM}
Symposium on Discrete Algorithms ({SODA})",
pages = "267--276",
year = "2002",
}
@InProceedings{PRS02,
author = "S. Pettie and V. Ramachandran and S. Sridhar",
title = "Experimental evaluation of a new shortest path algorithm",
booktitle = "Proc. 4th Workshop on Algorithm Engineering and Experiments
({ALENEX}), {LNCS} Vol. 2409",
pages = "126--142",
year = "2002",
}
@inproceedings{PR00,
author = "S. Pettie and V. Ramachandran",
title = "An optimal minimum spanning tree algorithm",
booktitle = "Proceedings of {ICALP} 2000 ({LNCS} Vol. 1853)",
pages = "49--60",
year = "2000",
}
@inproceedings{PR99,
author = "S. Pettie and V. Ramachandran",
title = "A randomized time-work optimal parallel algorithm for
finding a minimum spanning forest",
booktitle = "Proceedings of {RANDOM}-{APPROX}'99 ({LNCS} Vol. 1671)",
pages = "233--244",
year = "1999",
}
Technical Reports
@techreport{CU-CS-928-02,
author = "H. Gabow and S. Pettie",
title = "The Dynamic Vertex Minimum Problem and Its Application
to Clustering-type Approximation Algorithms",
institution = "University of Colorado, Boulder",
type = "Technical Report",
number = "CU-CS-928-02",
bibdate = apr,
year = "2002",
}
@TechReport{Pet-TR23,
year = "1999",
type = "Technical Report",
number = "CS-TR-99-23",
institution = "University of Texas, Austin",
title = "Finding minimum spanning trees in {$O(m\alpha(m,n))$} time",
bibdate = "October 21, 99",
url = "ftp://ftp.cs.utexas.edu/pub/techreports/tr99-23.ps.Z",
author = "S. Pettie",
abstract = "We describe a deterministic minimum spanning tree
algorithm running in time $O(m \alpha(m,n))$, where alpha
is a natural inverse of Ackermann's function and m and
n are the number of edges and vertices, respectively.
This improves upon the $O(m \alpha(m,n) \log \alpha(m,n))$
bound established by Chazelle in 1997. A similar $O(m
\alpha(m,n))$-time algorithm was discovered independently
by Chazelle, predating the algorithm presented here by
many months. This paper may still be of interest for
its alternative exposition.",
}