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{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},
	issue		= {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},
	issue		= {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},
	issue		= {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},
	issue		= {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},
	issue	= {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},
  issue		= {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{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		= {?},
	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		= {?},
	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     	= {?},
	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.",
}