dblp.uni-trier.dewww.uni-trier.de

Seth Pettie

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo

2009
34EERan Duan, Seth Pettie: Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. SODA 2009: 384-391
33EERan Duan, Seth Pettie: Dual-failure distance and connectivity oracles. SODA 2009: 506-515
2008
32EEJoseph L. Greathouse, Ilya Wagner, David A. Ramos, Gautam Bhatnagar, Todd M. Austin, Valeria Bertacco, Seth Pettie: Testudo: Heavyweight security analysis via statistical sampling. MICRO 2008: 117-128
31EESeth Pettie: Distributed algorithms for ultrasparse spanners and linear size skeletons. PODC 2008: 253-262
30EESeth Pettie: Splay trees, Davenport-Schinzel sequences, and the deque conjecture. SODA 2008: 1115-1124
29EERan Duan, Seth Pettie: Bounded-leg distance and reachability oracles. SODA 2008: 436-445
28EEZvi Lotker, Boaz Patt-Shamir, Seth Pettie: Improved distributed approximate matching. SPAA 2008: 129-136
27EESeth Pettie: All Pairs Shortest Paths in Sparse Graphs. Encyclopedia of Algorithms 2008
26EESeth Pettie: Minimum Spanning Trees. Encyclopedia of Algorithms 2008
25EESeth Pettie: Single-Source Shortest Paths. Encyclopedia of Algorithms 2008
24EESeth Pettie, Vijaya Ramachandran: Randomized minimum spanning tree algorithms using exponentially fewer random bits. ACM Transactions on Algorithms 4(1): (2008)
2007
23EESeth Pettie: Low Distortion Spanners. ICALP 2007: 78-89
22EESeth Pettie: Sources of Superlinearity in Davenport-Schinzel Sequences CoRR abs/0707.1715: (2007)
21EESeth Pettie: Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture CoRR abs/0707.2160: (2007)
2006
20EESeth Pettie: Towards a Final Analysis of Pairing Heaps. Data Structures 2006
19EESeth Pettie: An Inverse-Ackermann Type Lower Bound For Online Minimum Spanning Tree Verification. Combinatorica 26(2): 207-230 (2006)
2005
18EESeth Pettie: Towards a Final Analysis of Pairing Heaps. FOCS 2005: 174-183
17EESeth Pettie: Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time. ISAAC 2005: 964-973
16EESurender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie: New constructions of (alpha, beta)-spanners and purely additive spanners. SODA 2005: 672-681
15EEChristian Worm Mortensen, Seth Pettie: The Complexity of Implicit and Space Efficient Priority Queues. WADS 2005: 49-60
14EESeth Pettie, Vijaya Ramachandran: A Shortest Path Algorithm for Real-Weighted Undirected Graphs. SIAM J. Comput. 34(6): 1398-1431 (2005)
2004
13EESeth Pettie, Peter Sanders: A simpler linear time 2/3-epsilon approximation for maximum weight matching. Inf. Process. Lett. 91(6): 271-276 (2004)
12EESeth Pettie: A new approach to all-pairs shortest paths on real-weighted graphs. Theor. Comput. Sci. 312(1): 47-74 (2004)
2002
11EESeth Pettie, Vijaya Ramachandran, Srinath Sridhar: Experimental Evaluation of a New Shortest Path Algorithm. ALENEX 2002: 126-142
10EESeth Pettie: An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree. FOCS 2002: 155-
9EESeth Pettie: A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs. ICALP 2002: 85-97
8EESeth Pettie: On the Comparison-Addition Complexity of All-Pairs Shortest Paths. ISAAC 2002: 32-43
7EESeth Pettie, Vijaya Ramachandran: Computing shortest paths with comparisons and additions. SODA 2002: 267-276
6EESeth Pettie, Vijaya Ramachandran: Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms. SODA 2002: 713-722
5EEHarold N. Gabow, Seth Pettie: The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms. SWAT 2002: 190-199
4EESeth Pettie, Vijaya Ramachandran: An optimal minimum spanning tree algorithm. J. ACM 49(1): 16-34 (2002)
3EESeth Pettie, Vijaya Ramachandran: A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest. SIAM J. Comput. 31(6): 1879-1895 (2002)
2000
2EESeth Pettie, Vijaya Ramachandran: An Optimal Minimum Spanning Tree Algorithm. ICALP 2000: 49-60
1999
1 Seth Pettie, Vijaya Ramachandran: A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest. RANDOM-APPROX 1999: 233-244

Coauthor Index

1Todd M. Austin [32]
2Surender Baswana [16]
3Valeria Bertacco [32]
4Gautam Bhatnagar [32]
5Ran Duan [29] [33] [34]
6Harold N. Gabow [5]
7Joseph L. Greathouse [32]
8Telikepalli Kavitha [16]
9Zvi Lotker [28]
10Kurt Mehlhorn [16]
11Christian Worm Mortensen [15]
12Boaz Patt-Shamir [28]
13Vijaya Ramachandran [1] [2] [3] [4] [6] [7] [11] [14] [24]
14David A. Ramos [32]
15Peter Sanders [13]
16Srinath Sridhar [11]
17Ilya Wagner [32]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)