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{ChangPSZ21,
author = {Yi-Jun Chang and Seth Pettie and Thatchaphol Saranurak and Hengjie Zhang},
title = {Near-optimal Distributed Triangle Enumeration via Expander Decompositions},
journal = {J. ACM},
volume = {68},
number = {3},
year = {2021},
pages = {21:1--21:36},
}
@article{HuangPZZ21,
author = {Dawei Huang and Seth Pettie and Yixiang Zhang and Zhijun Zhang},
title = {The Communication Complexity of Set Intersection and Multiple Equality Testing},
journal = {{SIAM} J. Comput.},
volume = {50},
number = {2},
pages = {674--717},
year = {2021},
doi = {https://doi.org/10.1137/20M1326040},
}
@article{DuanP20,
author = {Ran Duan and
Seth Pettie},
title = {Connectivity Oracles for Graphs Subject to Vertex Failures},
journal = {{SIAM} J. Comput.},
volume = {49},
number = {6},
pages = {1363--1396},
year = {2020},
doi = {10.1137/17M1146610},
}
@article{ChangLP20,
author = {Yi{-}Jun Chang and
Wenzheng Li and
Seth Pettie},
title = {Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering},
journal = {{SIAM} J. Comput.},
volume = {49},
number = {3},
pages = {497--539},
year = {2020},
doi = {10.1137/19M1249527},
}
@article{HuangYPM19,
author = {Dawei Huang and
Dong Young Yoon and
Seth Pettie and
Barzan Mozafari},
title = {Join on Samples: {A} Theoretical Guide for Practitioners},
journal = {Proc. {VLDB} Endow.},
volume = {13},
number = {4},
pages = {547--560},
year = {2019},
}
@article{ChangHLPU20,
author = {Y.-J. Chang and
Q. He and
W. Li and
S. Pettie and
J. Uitto},
title = {Distributed Edge Coloring and a Special Case of the Constructive {L}ov{\'{a}}sz
Local Lemma},
journal = {{ACM} Transactions on Algorithms},
volume = {16},
number = {1},
pages = {8:1--8:51},
year = {2020},
doi = {10.1145/3365004},
}
@article{ChangKPWZ19,
author = {Y.-J. Chang and
T. Kopelowitz and
S. Pettie and
R. Wang and
W. Zhan},
title = {Exponential Separations in the Energy Complexity of Leader Election},
journal = {{ACM} Transactions on Algorithms},
volume = {15},
number = {4},
pages = {49:1--49:31},
year = {2019},
doi = {10.1145/3341111},
}
@article{HuangP19,
author = {Shang{-}En Huang and
Seth Pettie},
title = {{T}horup-{Z}wick emulators are universally optimal hopsets},
journal = {Inf. Process. Lett.},
volume = {142},
pages = {9--13},
year = {2019},
doi = {10.1016/j.ipl.2018.10.001},
}
@article{AmirKLPPS19,
author = {A. Amir and T. Kopelowitz and A. Levy and S. Pettie
and E. Porat and B. Riva Shalom},
title = {Mind the Gap! {O}nline Dictionary Matching with One Gap},
journal = {Algorithmica},
volume = {81},
number = {6},
pages = {2123--2157},
year = {2019},
}
@article{ChangP19,
author = {Y.-J. Chang and S. Pettie},
title = {A Time Hierarchy Theorem for the {LOCAL} Model},
journal = {SIAM J.~Comput.},
volume = {48},
number = {1},
pages = {33--69},
year = {2019},
}
@article{ChangKP19,
author = {Y.-J. Chang and
T. Kopelowitz and
S. Pettie},
title = {An Exponential Separation between Randomized and Deterministic Complexity
in the {LOCAL} Model},
journal = {{SIAM} J. Comput.},
volume = {48},
number = {1},
pages = {122--143},
year = {2019},
doi = {10.1137/17M1117537},
}
@article{AbboudBP18,
author = {A. Abboud and G. Bodwin and S. Pettie},
title = {A hierarchy of lower bounds for sublinear additive spanners},
journal = {SIAM J. Comput.},
year = {2018},
volume = {47},
number = {6},
pages = {2203--2236},
}
@article{HuangP19,
author = {S.-E. Huang and S. Pettie},
title = {{T}horup-{Z}wick emulators are universally optimal hopsets},
journal = {Information Processing Letters},
volume = {142},
pages = {9--13},
year = {2019},
}
@article{BenderKPY18,
author = {M. Bender and T. Kopelowitz and S. Pettie and M. Young},
title = {Contention resolution with constant throughput and log-logstar channel accesses},
journal = {SIAM J. Comput.},
year = {2018},
volume = {47},
number = {5},
pages = {1735--1754},
}
@article{WellmanP18,
author = {J. Wellman and S. Pettie},
title = {Lower Bounds on {D}avenport-{S}chinzel Sequences via Rectangular
{Z}arankiewicz Matrices},
journal = {Discrete Mathematics},
year = {2018},
volume = {341},
number = {7},
pages = {1987--1993},
}
@article{DuanPS18,
author = {R. Duan and S. Pettie and H.-H. Su},
title = {Scaling Algorithms for Weighted Matching in General Graphs},
journal = {ACM Transactions on Algorithms},
year = {2018},
volume = {14},
number = {1},
note = {Article 8},
}
@article{GronlundP18,
author = {A. Gr\o nlund and S. Pettie},
title = {Threesomes, degenerates, and love triangles},
journal = {J. ACM},
volume = {65},
number = {4},
note = {Article 22},
year = {2018},
}
@article{KingPSY18,
author = {V. King and S. Pettie and J. Saia and M. Young},
title = {A Resource-competitive Jamming Defense},
journal = {Distributed Computing},
volume = {31},
number = {6},
pages = {419--439},
year = {2018},
}
@article{ChungPS17,
author = {K.-M. Chung and S. Pettie and H.-H. Su},
title = {Distributed Algorithms for the {L}ov\'{a}sz Local Lemma and Graph Coloring},
journal = {Distributed Computing},
volume = {30},
number = {4},
pages = {261--280},
year = {2017},
}
@article{BEPS16,
author = {L. Barenboim and M. Elkin and S. Pettie and J. Schneider},
title = {The Locality of Distributed Symmetry Breaking},
journal = {J. ACM},
volume = {63},
number = {3},
note = {Article 20},
year = {2016},
}
@article{ElkinP16,
author = {S. Pettie},
title = {A Linear Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs},
journal = {ACM Transactions on Algorithms},
volume = {12},
number = {4},
note = {Article 50},
year = {2016},
}
@article{Pettie-DS,
author = {S. Pettie},
title = {Sharp Bounds on {D}avenport-{S}chinzel Sequences of Every Order},
journal = {J. ACM},
volume = {62},
number = {5},
note = {Article 36},
year = {2015},
}
@article{LotkerPP-distrmatch,
author = {Z. Lotker and B. Patt-Shamir and S. Pettie},
title = {Improved Distributed Approximate Matching},
journal = {J. ACM},
volume = {62},
number = {5},
note = {Article 38},
year = {2015},
}
@article{Pettie-FormFree,
author = {S. Pettie},
title = {Three Generalizations of {D}avenport-{S}chinzel Sequences},
journal = {SIAM J. Discr. Math.},
volume = {29},
number = {4},
pages = {2189—2238},
year = {2015},
}
@article{Pettie15-sensitivity,
author = {S. Pettie},
title = {Sensitivity Analysis of Minimum Spanning Trees in Sub-Inverse-{A}ckermann Time},
journal = {J. Graph Algorithms and Applications},
volume = {19},
number = {1},
pages = {375--391},
year = {2015},
}
@article{PettieS-trianglefree,
author = {S. Pettie and H.-H. Su},
title = {Distributed algorithms for coloring triangle-free graphs},
journal = {Information and Computation},
volume = {243},
year = {2015},
pages = {263--280},
}
@article{DuanP-approxMWM,
author = {R. Duan and S. Pettie},
title = {Linear Time Approximation for Maximum Weight Matching},
journal = {J. ACM},
volume = {61},
number = {1},
note = {Article 1},
year = {2014},
}
@article{Pettie-MCM-to-MWM,
author = {S. Pettie},
title = {A Simple Reduction from Maximum Weight Matching to Maximum Cardinality Matching},
journal = {Information Processing Letters},
year = {2012},
volume = {112},
number = {23},
pages = {893-898},
}
@article{Pettie-FH,
author = {S. Pettie},
title = {Degrees on Nonlinearity in Forbidden 0-1 Matrix Problems},
journal = {Discrete Mathematics},
year = {2011},
volume = {311},
pages = {2396--2410},
}
@article{Pettie-GenDS,
author = {S. Pettie},
title = {Generalized Davenport-Schinzel Sequences and Their 0-1 Matrix Counterparts},
journal = {J. Comb. Theory Ser. A},
year = {2011},
volume = {118},
number = {6},
pages = {1863--1895},
}
@article{Pettie-DS-nonlin,
author = {S. Pettie},
title = {Origins of Nonlinearity in Davenport-Schinzel Sequences},
journal = {SIAM J. Discrete Mathematics},
year = {2011},
volume = {25},
number = {1},
pages = {211--233},
}
@article{Pettie-Distr-Spanner,
author = {S. Pettie},
title = {Distributed Algorithms for Ultrasparse Spanners and Linear Size Skeletons},
journal = {Distributed Computing},
volume = {22},
number = {3},
year = {2010},
pages = {147--166},
}
@article{Pettie-Low-Dist-Span,
author = {S. Pettie},
title = {Low Distortion Spanners},
journal = {ACM Transactions on Algorithms},
volume = {6},
number = {1},
year = {2009},
}
@article{BaswanaKMP,
author = {S. Baswana and T. Kavitha and K. Mehlhorn and S. Pettie},
title = {Additive Spanners and $(\alpha,\beta)$-Spanners},
journal = {ACM Transactions on Algorithms},
volume = {7},
number = {1},
year = {2010},
}
@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{ChangDHP20,
author = {Yi{-}Jun Chang and
Varsha Dani and
Thomas P. Hayes and
Seth Pettie},
title = {The Energy Complexity of {BFS} in Radio Networks},
booktitle = {Proceedings 39th {ACM} Symposium on Principles of Distributed Computing (PODC)},
pages = {273--282},
year = {2020},
doi = {10.1145/3382734.3405713},
}
@inproceedings{HuangPZZ20,
author = {Dawei Huang and
Seth Pettie and
Yixiang Zhang and
Zhijun Zhang},
title = {The Communication Complexity of Set Intersection and Multiple Equality
Testing},
booktitle = {Proceedings 31st {ACM-SIAM} Symposium on Discrete Algorithms (SODA)},
pages = {1715--1732},
year = {2020},
doi = {10.1137/1.9781611975994.105},
}
@inproceedings{ChangJP19,
author = {Y.-J. Chang and W. Jin and S. Pettie},
title = {Simple contention resolution via multiplicative weight updates},
booktitle = {Proceedings 2nd Symposium on Simplicity in Algorithms (SOSA)},
year = {2019},
pages = {16:1--16:16},
}
@inproceedings{ChangPZ19,
author = {Y.-J. Chang and S. Pettie and H. Zhang},
title = {Distributed triangle detection via expander decomposition},
booktitle = {Proceedings 30th ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = {2019},
pages = {821--840},
}
@inproceedings{BrandtPU18,
author = {S. Brandt and S. Pettie and J. Uitto},
title = {Fine-grained Lower Bounds on Cops and Robbers},
booktitle = {Proceedings 26th European Symposium on Algorithms (ESA)},
pages = {9:1--9:12},
year = {2018},
}
@inproceedings{DorfmanKKPZ18,
author = {D. Dorfman and H. Kaplan and L. Kozma and S. Pettie and U. Zwick},
title = {Improved Bounds for Multipass Pairing Heaps and Path-balanced Binary Search Trees},
booktitle = {Proceedings 26th European Symposium on Algorithms (ESA)},
pages = {24:1--24:13},
year = {2018},
}
@inproceedings{ChangDHHLP18,
author = {Y.-J. Chang and V. Dani and T. Hayes and Q. He and W. Li and S. Pettie},
title = {The Energy Complexity of Broadcast},
booktitle = {Proceedings 37th ACM Symposium on Principles of Distributed Computing},
pages = {95--104},
year = {2018},
}
@inproceedings{HuangP18,
author = {S.-E. Huang and S. Pettie.},
title = {Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing Shortcuts},
booktitle = {Proceedings 16th Scandinavian Symposium and Workshops on Algorithm Theory},
pages = {26:1-26:12},
year = {2018},
}
@inproceedings{ChangLP18,
author = {Y.-J. Chang and W. Li and S. Pettie},
title = {An optimal distributed $(\Delta+1)$-coloring algorithm?},
booktitle = {Proceedings 50th ACM Symposium on Theory of Computing (STOC)},
pages = {445--456},
year = {2018},
}
@inproceedings{ChangHLPU18,
author = {Y.-J. Chang and Q. He and W. Li and S. Pettie and J. Uitto},
title = {The complexity of distributed edge coloring with small palettes},
booktitle = {Proceedings 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
pages = {2633--2652},
year = {2018},
}
@inproceedings{ChangP17,
author = {Y.-J. Chang and S. Pettie},
title = {A Time Hierarchy Theorem for the {LOCAL} Model},
booktitle = {Proceedings 58th IEEE Symposium on Foundations of Computer Science (FOCS)},
pages = {156-167},
year = {2017},
}
@inproceedings{CKPWZ17,
author = {Y.-J. Chang and T. Kopelowitz and S. Pettie and R. Wang and W. Zhan},
title = {Exponential Separations in the Energy Complexity of Leader Election},
booktitle = {Proceedings 49th ACM Symposium on Theory of Computing (STOC)},
pages = {771-783},
year = {2017},
}
@inproceedings{BernsteinKPPS17,
author = {A. Bernstein and T. Kopelowitz and S. Pettie and E. Porat and C. Stein},
title = {Simultaneously load balancing for every $p$-norm, with reassignments},
booktitle = {Proceedings of the 8th Conference on Innovations in Theoretical Computer Science ({ITCS})},
pages = {51:1-51:14},
year = {2017},
}
@inproceedings{HuangHKP17,
author = {S.-E. Huang and D. Huang and T. Kopelowitz and S. Pettie},
title = {Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time},
booktitle = {Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
pages = {510--520},
year = {2017},
}
@inproceedings{DuanP17,
author = {R. Duan and S. Pettie},
title = {Connectivity Oracles for Graphs Subject to Vertex Failures},
booktitle = {Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
pages = {490--509},
year = {2017},
}
@inproceedings{DuanPS17,
author = {R. Duan and S. Pettie and H.-H. Su},
title = {Scaling Algorithms for Weighted Matching in General Graphs},
booktitle = {Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
pages = {781--800},
year = {2017},
}
@inproceedings{AbboudBP17,
author = {A. Abboud and G. Bodwin and S. Pettie},
title = {A Hierarchy of Lower Bounds for Sublinear Additive Spanners},
booktitle = {Proceedings 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
pages = {568--576},
year = {2017},
}
@inproceedings{AmirKLPPS16,
author = {A. Amir and T. Kopelowitz and A. Levy and S. Pettie \
and E. Porat and B. Riva Shalom},
title = {Mind the Gap: Essentially Optimal Algorithms for Online
Dictionary Matching with One Gap},
booktitle = {Proceedings 27th International Symposium on Algorithms and Computation (ISAAC)},
pages = {12:1--12:12},
year = {2016},
doi = {10.4230/LIPIcs.ISAAC.2016.12},
}
@inproceedings{CKP16,
author = {Y.-J. Chang and T. Kopelowitz and S. Pettie},
title = {An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model},
booktitle = {Proceedings 57th IEEE Symposium on Foundations of Computer Science (FOCS)},
pages = {615--624},
year = {2016},
}
@inproceedings{KKPT16,
author = {C. Kejlberg-Rasmussen and T. Kopelowitz and S. Pettie and M. Thorup},
title = {Faster Worst Case Deterministic Dynamic Connectivity},
booktitle = {Proceedings 24th European Symposium on Algorithms (ESA)},
pages = {53:1--53:15},
year = {2016},
}
@inproceedings{BKPY16,
author = {M. Bender and T. Kopelowitz and S. Pettie and M. Young},
title = {Contention Resolution with Log-Logstar Channel Accesses},
booktitle = {Proceedings 48th ACM Symposium on Theory of Computing (STOC)},
pages = {499--508},
year = {2016},
}
@inproceedings{KopelowitzPP16,
author = {T. Kopelowitz and S. Pettie and E. Porat},
title = {Higher Lower Bounds from the 3SUM Conjecture},
booktitle = {Proceedings 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = {2016},
pages = {1272--1287},
}
@inproceedings{KopelowitzPP15,
author = {T. Kopelowitz and S. Pettie and E. Porat},
title = {Dynamic Set Intersection},
booktitle = {Proceedings 14th Int'l Symposium on Algorithms and Data Structures (WADS)},
year = {2015},
pages = {470--481},
}
@inproceedings{ElkinP15,
author = {M. Elkin and S. Pettie},
title = {A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs},
booktitle = {Proceedings 26th Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA})},
pages = {805--821},
year = {2015},
}
@inproceedings{Pettie15,
author = {S. Pettie},
title = {Sharp Bounds on Formation-free Sequences},
booktitle = {Proceedings 26th Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA})},
pages = {592--604},
year = {2015},
}
@inproceedings{ElkinPS15,
author = {M. Elkin and S. Pettie and H.-H. Su},
title = {$(2\Delta - l)$-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting},
booktitle = {Proceedings 26th Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA})},
pages = {355--370},
year = {2015},
}
@inproceedings{GronlundP14,
author = {A. Gr\o nlund and S. Pettie},
title = {Threesomes, degenerates, and love triangles},
booktitle = {Proceedings 55th IEEE Symposium on Foundations of Computer Science (FOCS)},
pages = {621--630},
year = {2014},
}
@inproceedings{ChungPS14,
author = {K.-M. Chung and S. Pettie and H.-H. Su},
title = {Distributed Algorithms for the {L}ov\'{a}sz Local Lemma and Graph Coloring},
booktitle = {Proceedings 33rd ACM Symposium on Principles of Distributed Computing (PODC)},
year = {2014},
pages = {134--143},
}
@inproceedings{GilbertKPPSY14,
author = {S. Gilbert and V. King and S. Pettie and E. Porat and J. Saia and M. Young},
title = {(Near) Optimal Resource-Competitive Broadcast with Jamming},
booktitle = {Proceedings 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
year = {2014},
pages = {257--266},
}
@inproceedings{Pettie-DS13,
author = {S. Pettie},
title = {Sharp Bounds on {D}avenport-{S}chinzel Sequences of Every Order},
booktitle = {Proceedings 29th Annual Symposium on Computational Geometry (SOCG)},
year = {2013},
pages = {319--328},
note = {Full manuscript available at arXiv:1204.1086},
}
@inproceedings{PettieSu13,
author = {S. Pettie and H.-H. Su},
title = {Fast Distributed Coloring Algorithms for Triangle-Free Graphs},
booktitle = {Proceedings 40th Int'l Colloquium on Automata, Languages, and Programming (ICALP)},
year = {2013},
pages = {681--693},
}
@inproceedings{BEPS12,
author = {L. Barenboim and M. Elkin and S. Pettie and J. Schneider},
title = {The Locality of Distributed Symmetry Breaking},
booktitle = {Proceedings 53rd IEEE Symposium on Foundations of Computer Science (FOCS)},
year = {2012},
pages = {321-330},
note = {Full manuscript available at arXiv:1202.1983}
}
@inproceedings{BPW-N12,
author = {G. Borradaile and S. Pettie and C. Wulff-Nilsen},
title = {Connectivity Oracles for Planar Graphs},
booktitle = {Proceedings 13th Scandinavian Workshop on Algorithm Theory (SWAT)},
year = {2012},
pages = {316--327},
note = {Full manuscript available at arXiv:1204.4159},
}
@inproceedings{Pettie-Forbidden-Sequences-11,
author = {S. Pettie},
title = {On the structure and composition of forbidden sequences, with geometric applications},
booktitle = {Proceedings 27th Annual Symposium on Computational Geometry (SOCG)},
year = {2011},
pages = {370--379},
}
@inproceedings{DuanP10b,
author = {R. Duan and S. Pettie},
title = {Approximating Maximum Weight Matching in Near-Linear Time},
booktitle = {Proceedings 51st IEEE Symposium on Foundations of Computer Science (FOCS)},
year = {2010},
pages = {673--682},
}
@inproceedings{DuanP10,
author = {R. Duan and S. Pettie},
title = {Connectivity Oracles for Failure Prone Graphs},
booktitle = {Proceedings 42nd ACM Symposium on Theory of Computing (STOC)},
year = {2010},
pages = {465--474},
}
@inproceedings{Pettie-Forbidden-10,
author = {S. Pettie},
title = {Applications of Forbidden 0-1 Matrices to Search Tree- and Path Compression-Based Data Structures},
booktitle = {Proceedings 21st ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = {2010},
pages = {1457--1467}
}
@inproceedings{Pettie-FH-10,
author = {S. Pettie},
title = {On Nonlinear Forbidden 0-1 Matrices: A Refutation of a F\"{u}redi-Hajnal Conjecture},
booktitle = {Proceedings 21st ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = {2010},
pages = {875--885}
}
@inproceedings{DuanP09b,
author = {R. Duan and S. Pettie},
title = {Fast algorithms for ($\max$, $\min$)-matrix multiplication and
bottleneck shortest paths},
booktitle = {Proceedings 20th ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = {2009},
pages = {384--391},
}
@inproceedings{DuanP09a,
author = {R. Duan and S. Pettie},
title = {Dual-failure distance and connectivity oracles},
booktitle = {Proceedings 20th ACM-SIAM Symposium on Discrete Algorithms (SODA)},
year = {2009},
pages = {506--515},
}
@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 (PODC)},
year = {2008},
pages = {253--262},
}
@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 (SPAA)},
year = {2008},
pages = {129--136},
}
@inproceedings{DuanPettie08,
author = {R. Duan and S. Pettie},
title = {Bounded-leg Distance and Reachability Oracles},
booktitle = {Proc. 19th {ACM}-{SIAM} Symposium on Discrete Algorithms (SODA)},
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 (SODA)},
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.",
}