1 @inproceedings{ bender00lca,
2 author = "Michael A. Bender and Martin Farach-Colton",
3 title = "The {LCA} Problem Revisited",
4 booktitle = "Latin American Theoretical {INformatics}",
7 url = "citeseer.ist.psu.edu/bender00lca.html" }
9 @inproceedings{ frederickson91ambivalent,
10 author = "Greg N. Frederickson",
11 title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
12 booktitle = "{IEEE} Symposium on Foundations of Computer Science",
15 url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" }
17 @article{ tarjan:setunion,
18 author = {Robert E. Tarjan and Jan van Leeuwen},
19 title = {Worst-case Analysis of Set Union Algorithms},
26 doi = {http://doi.acm.org/10.1145/62.2160},
27 publisher = {ACM Press},
28 address = {New York, NY, USA},
31 @inproceedings { fw:transdich,
32 author = "M. Fredman and D. E. Willard",
33 title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}",
34 booktitle = "{Proceedings of FOCS'90}",
40 author = {Peter van Emde Boas},
41 title = {Preserving Order in a Forest in Less Than Logarithmic Time
43 journal = {Inf. Process. Lett.},
48 bibsource = {DBLP, http://dblp.uni-trier.de}
51 @article{ benamram:pm,
52 author = "Ben-Amram, Amir M.",
53 title = "What is a ``Pointer Machine''?",
54 journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
57 url = "citeseer.ist.psu.edu/ben-amram95what.html" }
59 @article{ matsui:planar,
60 author = "Tomomi Matsui",
61 title = "{The Minimum Spanning tree Problem on a Planar Graph}",
62 journal = "Discrete Applied Mathematics",
66 url = "citeseer.nj.nec.com/2319.html"
69 @article{ chazelle:ackermann,
70 author = "Bernard Chazelle",
71 title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
78 @article{ nesetril:history,
79 author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
80 title = "{Some remarks on the history of MST-problem}",
81 journal = "Archivum Mathematicum",
87 @article{ nesetril:boruvka,
88 author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
89 title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
90 journal = "Discrete Mathematics",
96 @incollection { nesetril:minors,
97 author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
98 title = "{Colorings and Homomorphisms of Minor Closed Classes}",
99 booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
100 editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
103 publisher = "Springer Verlag"
106 @article { boruvka:ojistem,
107 author = "Otakar Bor{\accent23u}vka",
108 title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
109 journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
113 note = "Czech with German summary"
116 @article { boruvka:networks,
117 author = "Otakar Bor{\accent23u}vka",
118 title = "{P\v{r}\'\i{}sp\v{e}vek k~\v{r}e\v{s}en\'\i{} ot\'azky ekonomick\'e stavby elektrovodn\'y{}ch s\'\i{}t\'\i{} (Contribution to the solution of a problem of economical construction of electric networks)}",
119 journal = "Elektronick\'y obzor",
126 @article { jarnik:ojistem,
127 author = "Vojt\v{e}ch Jarn\'\i{}k",
128 title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
129 journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
137 author = "Robert E. Tarjan",
138 title = "{Data structures and network algorithms}",
139 series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}",
145 @article { gh:history,
146 author = "R. L. Graham and P. Hell",
147 title = "{On the history of the minimum spanning tree problem}",
148 journal = "{Annals of the History of Computing}",
154 @techreport { pettie:ackermann,
155 author = "Seth Pettie",
156 title = "{Finding minimum spanning trees in $\O(m\alpha(m,n))$ time}",
157 institution = "Univ. of Texas at Austin",
163 @inproceedings { pettie:optimal,
164 author = "Seth Pettie and Vijaya Ramachandran",
165 title = "{An Optimal Minimum Spanning Tree Algorithm}",
166 booktitle = "{Proceedings of ICALP'2000}",
168 publisher = "Springer Verlag",
172 @article { pettie:alpha,
173 title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}},
176 publisher={University of Texas at Austin Austin, TX, USA}
179 @article { karger:randomized,
180 author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
181 title = "{Linear expected-time algorithms for connectivity problems}",
188 @article { frederickson:online,
189 author = "Greg N. Frederickson",
190 title = "{Data structures for on-line updating of minimum spanning trees}",
191 journal = "{SIAM Journal on Computing}",
198 author = "Martin Mare\v{s}",
199 title = "{Two linear time algorithms for MST on minor closed graph classes}",
200 journal = "{Archivum Mathematicum}",
206 @article{ ft:fibonacci,
207 author = {Michael L. Fredman and Robert Endre Tarjan},
208 title = {Fibonacci heaps and their uses in improved network optimization algorithms},
215 doi = {http://doi.acm.org/10.1145/28869.28874},
216 publisher = {ACM Press},
217 address = {New York, NY, USA},
220 @article{ komlos:verify,
221 author = {J{\'a}nos Koml{\'o}s},
222 title = {Linear verification for spanning trees.},
223 journal = {Combinatorica},
228 bibsource = {DBLP, http://dblp.uni-trier.de}
231 @inproceedings{ king:verify,
232 author = "Valerie King",
233 title = "A Simpler Minimum Spanning Tree Verification Algorithm",
234 booktitle = "Workshop on Algorithms and Data Structures",
237 url = "citeseer.ist.psu.edu/king95simpler.html" }
239 @article{ king:verifytwo,
240 title={{A Simpler Minimum Spanning Tree Verification Algorithm}},
241 author={King, Valerie},
242 journal={Algorithmica},
249 author = "Alexander Schrijver",
250 title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
251 series = "Algorithms and Combinatorics",
254 publisher = "Springer Verlag"
257 @inproceedings{ thorup:aczero,
258 author = {Mikkel Thorup},
259 title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
260 booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
262 isbn = {0-89871-538-5},
264 location = {Baltimore, Maryland},
265 publisher = {Society for Industrial and Applied Mathematics},
266 address = {Philadelphia, PA, USA},
269 @article{ kruskal:mst,
270 title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
271 author={Kruskal Jr, J.B.},
272 journal={Proceedings of the American Mathematical Society},
281 title={{Graph Theory}},
282 author={Diestel, R.},
284 publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.}
288 title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
290 journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
293 publisher={ACM Press New York, NY, USA}
296 @article{ graham:msthistory,
297 title={{On the history of the minimum spanning tree problem}},
298 author={Graham, R.L. and Hell, P.},
299 journal={Annals of the History of Computing},
306 @article{ cayley:trees,
307 title={{A theorem on trees}},
308 author={Cayley, Arthur},
309 journal={Quart. J. Math},
315 @article{ dijkstra:mst,
316 title={{A note on two problems in connexion with graphs}},
317 author = "Dijkstra, E. W.",
318 journal={Numerische Mathematik},
327 author = "Prim, R. C.",
328 title = "Shortest connection networks and some generalizations",
329 journal = "Bell System Technical Journal",
335 @article{ choquet:mst,
336 title={{Etude de certains r{\'e}seaux de routes}},
337 author={Choquet, Gustave},
338 journal={Comptes-rendus de l'Académie des Sciences},
345 @incollection { sollin:mst,
346 title={{Le trace de canalisation}},
348 booktitle={Programming, Games, and Transportation Networks},
349 editor={Berge, C. and Ghouilla-Houri, A.},
350 publisher={Wiley, New York},
355 @article{ boyer:cutting,
356 title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
357 author={Boyer, J.M. and Myrvold, W.J.},
358 journal={Journal of Graph Algorithms and Applications},
365 @inproceedings{ takaoka:twothree,
366 title={{Theory of 2-3 Heaps}},
367 author={Takaoka, T. and Christchurch, N. Z.},
368 booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON'99},
369 location={Tokyo, Japan},
372 publisher={Springer},
373 series={{Lecture Notes in Computer Science}},
377 @inproceedings{ takaoka:trinomial,
378 title={{Theory of Trinomial Heaps}},
379 author={Takaoka, Tadao},
380 booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
381 location={Sydney, Australia},
384 publisher={Springer},
385 series={{Lecture Notes in Computer Science}},
390 title={{Introduction to Algorithms}},
391 author={Leiserson, C.E. and Rivest, R.L. and Cormen, T.H. and Stein, C.},
393 publisher={McGraw-Hill}
396 @inproceedings{ pettie:onlineverify,
397 author = "S. Pettie",
398 title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
399 tree verification problem",
400 booktitle = "Proc. 43rd Annual Symp. on the Foundations of Computer Science, Vancouver, Canada",
402 url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
405 @article{ dixon:verify,
406 author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
407 title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
408 journal = "SIAM J. Comput.",
413 url = "citeseer.ist.psu.edu/dixon92verification.html"
416 inproceedings{ pettie:minirand,
417 author = {Seth Pettie and Vijaya Ramachandran},
418 title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
419 booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms},
421 isbn = {0-89871-513-X},
423 location = {San Francisco, California},
424 publisher = {Society for Industrial and Applied Mathematics},
425 address = {Philadelphia, PA, USA}
428 @article{ buchsbaum:verify,
429 title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
430 author={Buchsbaum, A.L. and Kaplan, H. and Rogers, A. and Westbrook, J.R.},
431 journal={Proceedings of the thirtieth annual ACM Symposium on Theory of Computing},
434 publisher={ACM Press New York, NY, USA}
437 @article{ bacala:parametric,
438 title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
439 author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
440 journal={Theoretical Computer Science},
448 @inproceedings{ katriel:cycle,
449 author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
450 title = "A practical minimum spanning tree algorithm using the cycle property",
451 booktitle = "11th European Symposium on Algorithms(ESA)",
455 publisher = "Springer",
457 url = "citeseer.ist.psu.edu/katriel03practical.html"
460 @article{ alstrup:nca,
461 title={{Nearest common ancestors: a survey and a new distributed algorithm}},
462 author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
463 journal={Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures},
466 publisher={ACM Press New York, NY, USA}
470 title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
471 author={Gabow, H.N. and Galil, Z. and Spencer, T. and Tarjan, R.E.},
472 journal={Combinatorica},
480 @Unpublished{ eisner:tutorial,
481 author = {Jason Eisner},
482 title = {State-of-the-Art Algorithms for Minimum Spanning
483 Trees: A Tutorial Discussion},
484 note = {Manuscript available online (78 pages), University of Pennsylvania},
486 url = {http://cs.jhu.edu/~jason/papers/#ms97},
490 title={{On finding lowest common ancestors in trees.}},
491 author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
492 journal={SIAM Journal on Computing},
498 @book{ knuth:fundalg,
499 author = {Donald E. Knuth},
500 title = {The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms},
502 isbn = {0-201-89683-4},
503 publisher = {Addison Wesley Longman Publishing Co., Inc.},
504 address = {Redwood City, CA, USA},
507 @book{ knuth:seminalg,
508 author = {Donald E. Knuth},
509 title = {The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical algorithms},
511 isbn = {978-0-201-89684-8},
512 publisher = {Addison Wesley Longman Publishing Co., Inc.},
513 address = {Redwood City, CA, USA},
516 @inproceedings{ hagerup:wordram,
517 author = {Torben Hagerup},
518 title = {{Sorting and Searching on the Word RAM}},
519 booktitle = {STACS '98: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science},
521 isbn = {3-540-64230-7},
523 publisher = {Springer-Verlag},
524 address = {London, UK},
527 @inproceedings{ cook:ram,
528 author = {Stephen A. Cook and Robert A. Reckhow},
529 title = {Time-bounded random access machines},
530 booktitle = {STOC '72: Proceedings of the fourth annual ACM Symposium on Theory of Computing},
533 location = {Denver, Colorado, United States},
534 doi = {http://doi.acm.org/10.1145/800152.804898},
536 address = {New York, NY, USA},
539 @book{ okasaki:funcds,
540 author = {Chris Okasaki},
541 title = {Purely Functional Data Structures},
543 publisher = {Cambridge University Press}
546 @book { intel:pentium,
547 author = {{Intel Corp.}},
548 title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference},
550 publisher = {Intel Corp.},
551 xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
554 @article{ hagerup:dd,
555 title={{Deterministic Dictionaries}},
556 author={Hagerup, T. and Miltersen, P.B. and Pagh, R.},
557 journal={J. Algorithms},
564 @article{ fredman:sst,
565 title={{Storing a Sparse Table with $\O(1)$ Worst Case Access Time}},
566 author={Fredman, M.L. and Koml{\'o}s, J. and Szemer{\'e}di, E.},
567 journal={Journal of the ACM (JACM)},
572 publisher={ACM Press New York, NY, USA}
575 @book{ motwani:randalg,
576 title={{Randomized Algorithms}},
577 author={Motwani, R. and Raghavan, P.},
579 publisher={Cambridge University Press}
583 title={{Surpassing the information theoretic bound with fusion trees}},
584 author={Fredman, M.L. and Willard, D.E.},
585 journal={Journal of Computer and System Sciences},
590 publisher={Academic Press, Inc. Orlando, FL, USA}
593 @article{ han:detsort,
594 title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}},
596 journal={Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing},
599 publisher={ACM Press New York, NY, USA}
602 @article{ hanthor:randsort,
603 title={{Integer Sorting in $\O(n\sqrt{\log\log n})$ Expected Time and Linear Space}},
604 author={Han, Y. and Thorup, M.},
605 journal={Proceedings of the 43rd Symposium on Foundations of Computer Science},
608 publisher={IEEE Computer Society Washington, DC, USA}
611 @article{ ito:newrap,
612 title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}},
613 author={Ito, M. and Takagi, N. and Yajima, S.},
614 journal={Proc. 12th IEEE Symp. Computer Arithmetic},