Seth Pettie
2260 Hayward St.
Department of EECS
University of Michigan
Ann Arbor, MI 48109
Office: CSE Building Room 3628
Phone: (734) 615-4210
Fax: (734) 763-1260
Curriculum Vitae: PDF
|
Seth Pettie 2260 Hayward St. Department of EECS University of Michigan Ann Arbor, MI 48109 Office: CSE Building Room 3628 Phone: (734) 615-4210 Fax: (734) 763-1260
Curriculum Vitae: PDF |
|
Professional Service: Steering Committee, SIAM Symposium on Simplicity in Algorithms (SOSA). Co-chair, SOSA 2024 which will be co-located with SODA 2024 in Alexandria, VA. Organizing Committee, Integer Programming and Combinatorial Optimization (IPCO 2019) Editorial Board, Algorithmica Editorial Board, The Encyclopedia of Algorithms PC Member of FOCS 2023, LATIN 2022, PODC 2022, SIROCCO 2022, SSS 2021, SODA 2021, ESA 2020, SWAT 2020, SSS 2019, STOC 2019, ISAAC 2018, SSS 2018, ITCS 2018, ICALP 2018, WADS 2017, STACS 2017, SPAA 2016, SWAT 2016, FOCS 2015, ESA 2015, ISAAC 2015, SIROCCO 2015, SPAA 2014, TAMC 2013, SODA 2013, STOC 2011, MFCS 2011, FSTTCS 2011, STACS 2008, ALENEX 2008, ESA 2007, SODA 2007, ICALP 2005, ALENEX 2005. Together with M. Lewenstein and V. V. Williams I organized a Dagstuhl workshop on Structure and Hardness in P, which was held in November 2016. Feel free to solve any of the 26 Open Problems that came out of this workshop. With R. Krauthgamer, B. Saha, and V. V. Williams I organized a Bertinoro Workshop on Fine-grained Approximation Algorithms and Complexity, held May 27-31, 2019. With David Bevan, Miklós Bóna, and István Miklós I organized a Dagstuhl workshop on Pattern Avoidance, Statistical Mechanics, and Computational Complexity, held March 19-24, 2023. Students, Postdocs, and Visitors Dingyu Wang (Ph.D. student) Leqi (Jimmy) Zhu (postdoc) Shang-En Huang (Ph.D 2022), now postdoc @ Boston College. Dawei Huang (Ph.D. 2020), now @ Google. Yi-Jun Chang (Ph.D. 2019), postdoc @ ETH Zurich, now Professor @ NUS Singapore. Winner of the 2020 Principles of Distributed Computing Doctoral Dissertation Award. Hsin-Hao Su (Ph.D. 2015), postdoc @ MIT, now Professor @ Boston College. Winner of the 2016 Principles of Distributed Computing Doctoral Dissertation Award. Tsvi Kopelowitz (postdoc), now Professor @ Bar-Ilan University. Ran Duan (Ph.D. 2011), postdoc @ MPI, now Professor @ IIIS, Tsinghua University Maxwell Young (postdoc), now Professor @ Mississippi State University; previously Professor @ Drexel University. Veronika Loitzenbauer, Visitor, June-August, 2016. Now researcher @ Johannes Kepler Universität Linz. Julian Wellman, Greenhills High School. Summer 2016. MIT Math, Fall 2017. Ruosong Wang, Tsinghua University. Visitor, February-June, 2016. Now Ph.D. student @ Carnegie Mellon University. Wei Zhan, Tsinghua University. Visitor, February-June, 2016. Now Ph.D. student @ Princeton University. Qizheng He, Tsinghua University. Visitor, March-August, 2017. Now Ph.D. student @ UIUC. Wenzheng Li, Tsinghua University. Visitor, March-August, 2017. Now Ph.D. student @ Stanford. Hengjie Zhang, Tsinghua University. Visitor, March-August, 2018. Now Ph.D. student @ Columbia University. Yixiang Zhang, Tsinghua University. Visitor, March-August, 2019. Zhijun Zhang, Tsinghua University. Visitor, March-August, 2019. Now Ph.D. student @ Princeton University. Longhui Yin, Tsinghua University. Visitor, February-August, 2020. Now Ph.D. student @ IIIS, Tsinghua. Yaowei Long, Tsinghua University. Visitor, February-August, 2020. Now Ph.D. student @ University of Michigan. Benyu Wang, Tsinghua University. Visitor, February-August, 2022. Zhiyi Huang, Tsinghua University. Visitor, February-August, 2022. See my Google Scholar and DBLP pages for more citation information. Manuscripts / In Submission Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection Shang-En Huang, Seth Pettie, and Leqi Zhu Journal submission: arXiv:2206.15335v2 Optimal Vertex Connectivity Oracles Seth Pettie, Thatchaphol Saranurak, and Longhui Yin Journal submission: arXiv:2201.00408 Fraud Detection for Random Walks Varsha Dani, Thomas Hayes, Seth Pettie, and Jared Saia Journal Articles Almost Optimal Exact Distance Oracles for Planar Graphs Panagiotis Charalampopoulos, Pawel Gawrychowski, Yaowei Long, Shay Mozes, Seth Pettie, Oren Weimann, and Christian Wulff-Nilsen J. ACM 70(2), Article 12, pp 1-50. Publisher's website Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup TheoretiCS, to appear. Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks Varsha Dani, Aayush Gupta, Thomas Hayes, and Seth Pettie Distributed Computing, 2022. arXiv:2104.09096 Publisher's website Approximate Generalized Matching: f-Factors and f-Edge Covers Dawei Huang and Seth Pettie Algorithmica 84(7):1952-1992, 2022. arXiv:1706.05761 Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing Shortcuts Shang-En Huang and Seth Pettie SIAM J. Discrete Mathematics 35(3):2129-2144, 2021. Near-optimal Distributed Triangle Enumeration via Expander Decompositions Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang J. ACM 68(3):1-36, 2021. Publisher's website The Communication Complexity of Set Intersection and Multiple Equality Testing Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun Zhang SIAM J. Comput. 50(2):674-717, 2021. Publisher's website. Connectivity Oracles for Graphs Subject to Vertex Failures Ran Duan and Seth Pettie SIAM J. Comput. 49(6):1363-1396, 2020. arXiv:1607.06865 Publisher's website Distributed (Δ +1)-Coloring via Ultrafast Graph Shattering Yi-Jun Chang, Wenzheng Li, Seth Pettie SIAM J. Comput. 49(3):497-539, 2020. Publisher's website Distributed Edge Coloring and a Special Case of the Constructive Lovasz Local Lemma Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto ACM Transactions on Algorithms 16(1), Article 8, 2020. Publisher's website Join on Samples: A Theoretical Guide for Practitioners Dawei Huang, Dong Young Yoon, Seth Pettie, and Barzan Mozafari Proceedings of the VLDB Endowment 13(4):547-560, 2019. Exponential Separations in the Energy Complexity of Leader Election Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan ACM Transactions on Algorithms 15(4), Article 49, 2019. Publisher's website An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie SIAM J. Comput. 48(1):122-143, 2019. Publisher's website Mind the Gap! Online Dictionary Matching with One Gap Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom Algorithmica 81(6):2123-2157, 2019. Publisher's website A Time Hierarchy Theorem for the LOCAL Model Yi-Jun Chang and Seth Pettie SIAM J. Comput. 48(1):33-69, 2019. Publisher's website, PDF A Hierarchy of Lower Bounds for Sublinear Additive Spanners Amir Abboud, Greg Bodwin, and Seth Pettie SIAM J. Comput. 47(6):2203-2236, 2018. Publisher's website, PDF Thorup-Zwick Emulators are Universally Optimal Hopsets Shang-En Huang and Seth Pettie Information Processing Letters 142, pp. 9-13, 2019. Publisher's website Contention Resolution with Constant Throughput and Log-Logstar Channel Accesses Michael Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young SIAM J. Comput. 47(5):1735-1754, 2018. Publisher's website, PDF Threesomes, Degenerates, and Love Triangles Allan Grønlund and Seth Pettie J. ACM 65(4), Article 22, 2018. Scaling Algorithms for Weighted Matching in General Graphs Ran Duan, Seth Pettie, and Hsin-Hao Su ACM Transactions on Algorithms 14(1), Article 8, 2018. Publisher website, PDF Lower Bounds on Davenport-Schinzel Sequences via Rectangular Zarankiewicz Matrices Julian Wellman and Seth Pettie Discrete Mathematics 341(7):1987-1993, 2018. arXiv:1610.09774 A Resource-competitive Jamming Defense Valerie King, Seth Pettie, Jared Saia, and Maxwell Young Distributed Computing 31(6):419-439, 2018. Publisher website, PDF Distributed Algorithms for the Lovász Local Lemma and Graph Coloring Kai-Min Chung, Seth Pettie, and Hsin-Hao Su Distributed Computing 30(4):261-280, 2017. Publisher website, PDF The Locality of Distributed Symmetry Breaking Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider J. ACM 63(3), Article 20, 2016. A Linear Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs Michael Elkin and Seth Pettie ACM Transactions on Algorithms 12(4), Article 50, 2016. Sharp Bounds on Davenport-Schinzel Sequences of Every Order Seth Pettie J. ACM 62(5), Article 36, 2015. Improved Distributed Approximate Matching Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie J. ACM 62(5), Article 38, 2015. Three Generalizations of Davenport-Schinzel Sequences Seth Pettie SIAM J. Discrete Mathematics 29(4):2189-2238, 2015. Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time Seth Pettie J. Graph Algorithms and Applications 19(1):375-391, 2015. Distributed Coloring Algorithms for Triangle-free Graphs Seth Pettie and Hsin-Hao Su Information and Computation 243:263-280, 2015. Linear Time Approximation for Maximum Weight Matching Ran Duan and Seth Pettie J. ACM 61(1), Article 1, 2014. A Simple Reduction from Maximum Weight Matching to Maximum Cardinality Matching Seth Pettie Information Processing Letters 112(23):893-898, 2012. Degrees of Nonlinearity in Forbidden 0-1 Matrix Problems Seth Pettie Discrete Mathematics 311, pp. 2396-2410, 2011. Journal submission: PDF Generalized Davenport-Schinzel Sequences and Their 0-1 Matrix Counterparts Seth Pettie J. Combinatorial Theory Series A 118(6):1863-1895, 2011. Origins of Nonlinearity in Davenport-Schinzel Sequences Seth Pettie SIAM J. Discrete Mathematics 25(1):211-233, 2011. Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons Seth Pettie Distributed Computing 22(3):147-166, 2010. Low Distortion Spanners Seth Pettie ACM Transactions on Algorithms 6(1), 2009. PDF, post-publication acknowledgement Additive Spanners and (α, β)-Spanners S. Baswana, T. Kavitha, K. Mehlhorn, and Seth Pettie ACM Transactions on Algorithms 7(1), 2010. Randomized Minimum Spanning Tree Algorithms Using Exponentially Fewer Random Bits Seth Pettie and Vijaya Ramachandran ACM Transactions on Algorithms 4(1):1-27, 2008. A Shortest Path Algorithm for Real-Weighted Undirected Graphs Seth Pettie and Vijaya Ramachandran SIAM J. Comput. 34(6):1398-1431, 2005. Link to article, PDF An Inverse-Ackermann Type Lower Bound for Online Minimum Spanning Tree Verification Seth Pettie Combinatorica 26(2):207-230, 2006. PostScript, PDF A Simpler Linear Time 2/3 - ε Approximation for Maximum Weight Matching Seth Pettie and Peter Sanders Information Processing Letters 91(6):271-276, 2004. PostScript, PDF A New Approach to All-Pairs Shortest Paths on Real-Weighted Graphs Seth Pettie Theoretical Computer Science, special issue on papers from ICALP 2002, 312(1):47-74, 2003. Link to article, PostScript, PDF An Optimal Minimum Spanning Tree Algorithm Seth Pettie and Vijaya Ramachandran J. ACM 49(1):16-34, 2002. Link to article, PostScript, PDF A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest Seth Pettie and Vijaya Ramachandran SIAM J. on Computing 31(6):1879-1895, 2002. Link to article, PostScript, PDF Conference Papers Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond Seth Pettie and Dingyu Wang PODS 2023 arXiv:2208.10578 Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection Shang-En Huang, Seth Pettie, and Leqi Zhu SODA 2023 arXiv:2206.15335 Optimal Vertex Connectivity Oracles Seth Pettie, Thatchaphol Saranurak, and Longhui Yin STOC 2022 arXiv:2201.00408 Byzantine Agreement in Polynomial Time with Near-Optimal Resilience Shang-En Huang, Seth Pettie Leqi Zhu STOC 2022 arXiv:2202.13452 Incremental SCC Maintenance in Sparse Graphs Aaron Bernstein, Aditi Dudeja, and Seth Pettie ESA 2021 PDF. Wake Up and Join Me! An Energy Efficient Algorithm for Maximal Matching in Radio Networks Varsha Dani, Aayush Gupta, Thomas Hayes, and Seth Pettie DISC 2021; Brief Announcement at PODC 2021. arXiv:2104.09096 Non-mergeable Sketching for Cardinality Estimation Seth Pettie, Dingyu Wang and Longhui Yin ICALP 2021 arXiv:2008.08739 The Structure of Minimum Vertex Cuts Seth Pettie and Longhui Yin ICALP 2021 arXiv:2102.06805 Information Theoretic Limits of Cardinality Estimation: Fisher meets Shannon Seth Pettie and Dingyu Wang STOC 2021 arXiv:2007.06865 Distance Oracles for Planar Graphs with Better Time-Space Tradeoffs Yaowei Long and Seth Pettie SODA 2021 arXiv:2007.08585 Contention Resolution without Collision Detection Michael Bender, Tsvi Kopelowitz, William Kuszmaul, Seth Pettie STOC 2020 Join on Samples: A Theoretical Guide for Practitioners Dawei Huang, Dong Young Yoon, Seth Pettie, and Barzan Mozafari Presented at VLDB 2020 The Energy Complexity of BFS in Radio Networks Yi-Jun Chang, Varsha Dani, Thomas Hayes, and Seth Pettie PODC 2020 Publisher's website The Communication Complexity of Set Intersection and Multiple Equality Testing Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun Zhang SODA 2020 arXiv:1908.11825 Simple Contention Resolution via Multiplicative Weight Updates Yi-Jun Chang, Wenyu Jin, and Seth Pettie SOSA 2019 Proceedings Distributed Triangle Detection via Expander Decomposition Yi-Jun Chang, Seth Pettie, and Hengjie Zhang SODA 2019 arXiv:1807.06624 Fine-grained Lower Bounds on Cops and Robbers Sebastian Brandt, Seth Pettie, and Jara Uitto ESA 2018 Improved Bounds for Multipass Pairing Heaps and Path-balanced Binary Search Trees Dani Dorfman, Haim Kaplan, Laszlo Kozma, Seth Pettie, and Uri Zwick ESA 2018 The Energy Complexity of Broadcast Yi-Jun Chang, Varsha Dani, Thomas Hayes, Qizheng He, Wenzheng Li, and Seth Pettie PODC 2018 arXiv:1710.01800 Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing Shortcuts Shang-En Huang and Seth Pettie SWAT 2018 arXiv:1802.06271 An Optimal Distributed (Δ +1)-Coloring Algorithm? Yi-Jun Chang, Wenzheng Li, and Seth Pettie STOC 2018 arXiv:1711.01361 The Complexity of Distributed Edge Coloring with Small Palettes Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto SODA 2018 arXiv:1708.04290 A Time Hierarchy Theorem for the LOCAL Model Yi-Jun Chang and Seth Pettie FOCS 2017 arXiv:1704.06297 A 1-hour version at TCS+. Invited presentation (PDF) at HALG 2018. Exponential Separations in the Energy Complexity of Leader Election Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, Wei Zhan STOC 2017 arXiv:1609.08486v2 Fully Dynamic Connectivity in O(log n (log log n)2) Amortized Expected Time Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, and Seth Pettie SODA 2017 arXiv:1609.05867 A Hierarchy of Lower Bounds for Sublinear Additive Spanners Amir Abboud, Greg Bodwin, and Seth Pettie SODA 2017 arXiv:1607.07497 Connectivity Oracles for Graphs Subject to Vertex Failures Ran Duan and Seth Pettie SODA 2017 arXiv:1607.06865 Scaling Algorithms for Weighted Matching in General Graphs Ran Duan, Seth Pettie, and Hsin-Hao Su SODA 2017 arXiv:1411.1919v5 Simultaneously Load Balancing for Every p-norm, With Reassignments Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, and Cliff Stein ITCS 2017 Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom ISAAC 2016 arXiv:1503.07563 An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie FOCS 2016 arXiv:1602.08166 Faster Worst Case Deterministic Dynamic Connectivity Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup ESA 2016 arXiv:1507.05944v2 Contention Resolution with Log-Logstar Channel Accesses Michael Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young STOC 2016 Higher Lower Bounds from the 3SUM Conjecture Tsvi Kopelowitz, Seth Pettie, and Ely Porat SODA 2016 arXiv:1407.6756 Dynamic Set Intersection Tsvi Kopelowitz, Seth Pettie, and Ely Porat WADS 2015 (2Δ-1)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting Michael Elkin, Seth Pettie, and Hsin-Hao Su SODA 2015 Sharp Bounds on Formation-free Sequences Seth Pettie SODA 2015 See journal version: Three Generalizations of Davenport-Schinzel Sequences. A Linear Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs Michael Elkin and Seth Pettie SODA 2015 See journal version. Threesomes, Degenerates, and Love Triangles Allan Grønlund, Seth Pettie FOCS 2014 arXiv:1404.0799 Distributed Algorithms for the Lovász Local Lemma and Graph Coloring Kai-Min Chung, Seth Pettie, and Hsin-Hao Su PODC 2014 See journal submission. (Near) Optimal Resource-Competitive Broadcast with Jamming Seth Gilbert, Valerie King, Seth Pettie, Ely Porat, Jared Saia, and Maxwell Young SPAA 2014 Sharp Bounds on Davenport-Schinzel Sequences of Every Order Seth Pettie SoCG 2013 See journal version. Conference presentation (extended) PPTX Fast Distributed Coloring Algorithms for Triangle-Free Graphs Seth Pettie and Hsin-Hao Su ICALP 2013 See journal version. The Locality of Distributed Symmetry Breaking Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider FOCS 2012 See journal version. Connectivity Oracles for Planar Graphs Glencora Borradaile, Seth Pettie, and Christian Wulff-Nilsen SWAT 2012 arXiv:1204.4159 On the Structure and Composition of Forbidden Sequences, with Geometric Applications Seth Pettie SoCG 2011 Approximating Maximum Weight Matching in Near-linear Time Ran Duan and Seth Pettie FOCS 2010 See journal version. Connectivity Oracles for Failure Prone Graphs Ran Duan and Seth Pettie STOC 2010 See journal version. On Nonlinear Forbidden 0-1 Matrices: A Refutation of a Furedi-Hajnal Conjecture Seth Pettie SODA 2010 See journal version: Degrees of Nonlinearity in Forbidden 0-1 Matrix Problems. Applications of Forbidden 0-1 Matrices to Search Tree- and Path Compression-Based Data Structures Seth Pettie SODA 2010 Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths Ran Duan and Seth Pettie SODA 2009 Dual-Failure Distance and Connectivity Oracles Ran Duan and Seth Pettie SODA 2009 Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons Seth Pettie PODC 2008 See journal version. Improved Distributed Approximate Matching Zvi Lotker, Boaz Patt-Shamir, Seth Pettie SPAA 2008 See journal version. Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture Seth Pettie SODA 2008 Bounded-leg Distance and Reachability Oracles Ran Duan and Seth Pettie SODA 2008 Low Distortion Spanners Seth Pettie ICALP 2007 See journal version. Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-Ackermann Time Seth Pettie ISAAC 2005 See journal version. Towards a Final Analysis of Pairing Heaps Seth Pettie FOCS 2005 The Complexity of Implicit and Space-Efficient Priority Queues Christian Mortensen and Seth Pettie WADS 2005 PostScript New Constructions of (α, β)-Spanners and Purely Additive Spanners S. Baswana, T. Kavitha, K. Mehlhorn, and Seth Pettie Proceedings 16th Symposium on Discrete Algorithms (SODA 2005) See journal version. On the Comparison-Addition Complexity of All-pairs Shortest Paths Seth Pettie 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002). PostScript, PDF (See my Ph.D. thesis for the best exposition of this result.) An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree Verification Problem Seth Pettie 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002) See journal version. A Faster All-Pairs Shortest Path Algorithm for Real-Weighted Sparse Graphs Seth Pettie Proceedings 29th Int'l Colloq. on Automata, Languages, and Programming (ICALP 2002). Received Best Student Paper Award See journal version. The Dynamic Vertex Minimum Problem and its Application to Clustering-type Approximation Algorithms Harold Gabow and Seth Pettie Proceedings 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002). Link to paper, PostScript, PDF See technical report below. Experimental Evaluation of a New Shortest Path Algorithm Seth Pettie, Vijaya Ramachandran, and Srinath Sridhar Proceedings 4th Workshop on Algorithm Engineering and Experiments (ALENEX 2002). Link to paper, PostScript, PDF Minimizing Randomness in Minimum Spanning Tree, Parallel Connectivity, and Set Maxima Algorithms Seth Pettie and Vijaya Ramachandran Proceedings 13th Symposium on Discrete Algorithms (SODA 2002) See journal version. Computing Shortest Paths with Comparisons and Additions Seth Pettie and Vijaya Ramachandran Proceedings 13th Symposium on Discrete Algorithms (SODA 2002) See journal version. An Optimal Minimum Spanning Tree Algorithm Seth Pettie and Vijaya Ramachandran Proceedings 27th Int'l Colloq. on Automata, Languages, and Programming (ICALP 2000) Received Best Paper Award See journal version. A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest Seth Pettie and Vijaya Ramachandran Proceedings 3rd Int'l Workshop on Randomization and Approximation in Computer Science RANDOM 1999 See journal version. Theses and Technical Reports On the Shortest Path and Minimum Spanning Tree Problems Received The Outstanding Dissertation Award from The University of Texas Graduate School, 2004. The Dynamic Vertex Minimum Problem and its Application to Clustering-type Approximation Algorithms Harold Gabow and Seth Pettie Technical Report: PostScript, PDF, Finding Minimum Spanning Trees in O(m α(m,n)) Time Seth Pettie Technical Report: PostScript, PDF Other A bibliography of papers on graph matching and related topics. Some of these articles were rather difficult to obtain, so I thought I'd save you the trouble and collect them in one tidy list. Some travel photos
|
