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 @inproceedings{thorup03ac0,
52 author = {Mikkel Thorup},
53 title = {On AC0 implementations of fusion trees and atomic heaps},
54 booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
56 isbn = {0-89871-538-5},
58 location = {Baltimore, Maryland},
59 publisher = {Society for Industrial and Applied Mathematics},
60 address = {Philadelphia, PA, USA},
63 @article{ benamram95what,
65 title = "What is a ``Pointer Machine''?",
66 journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
69 url = "citeseer.ist.psu.edu/ben-amram95what.html" }
71 @article{ matsui:planar,
72 author = "Tomomi Matsui",
73 title = "{The Minimum Spanning tree Problem on a Planar Graph}",
74 journal = "Discrete Applied Mathematics",
78 url = "citeseer.nj.nec.com/2319.html"
81 @article{ chazelle:ackermann,
82 author = "Bernard Chazelle",
83 title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
90 @article{ nesetril:history,
91 author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
92 title = "{Some remarks on the history of MST-problem}",
93 journal = "Archivum Mathematicum",
99 @article{ nesetril:boruvka,
100 author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
101 title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
102 journal = "Discrete Mathematics",
103 volume = "233(1--3)",
108 @incollection { nesetril:minors,
109 author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
110 title = "{Colorings and Homomorphisms of Minor Closed Classes}",
111 booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
112 editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
115 publisher = "Springer Verlag"
118 @article { boruvka:ojistem,
119 author = "Otakar Bor{\accent23u}vka",
120 title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
121 journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
125 note = "Czech with German summary"
128 @article { boruvka:networks,
129 author = "Otakar Bor{\accent23u}vka",
130 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)}",
131 journal = "Elektronick\'y obzor",
138 @article { jarnik:ojistem,
139 author = "Vojt\v{e}ch Jarn\'\i{}k",
140 title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
141 journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
149 author = "Robert E. Tarjan",
150 title = "{Data structures and network algorithms}",
151 series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}",
157 @article { gh:history,
158 author = "R. L. Graham and P. Hell",
159 title = "{On the history of the minimum spanning tree problem}",
160 journal = "{Annals of the History of Computing}",
166 @techreport { pettie:ackermann,
167 author = "Seth Pettie",
168 title = "{Finding minimum spanning trees in $O(m\alpha(m,n))$ time}",
169 institution = "Univ. of Texas at Austin",
175 @inproceedings { pettie:optimal,
176 author = "Seth Pettie and Vijaya Ramachandran",
177 title = "{An Optimal Minimum Spanning Tree Algorithm}",
178 booktitle = "{Proceedings of ICALP'2000}",
180 publisher = "Springer Verlag",
184 @article { karger:randomized,
185 author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
186 title = "{Linear expected-time algorithms for connectivity problems}",
193 @article { frederickson:online,
194 author = "Greg N. Frederickson",
195 title = "{Data structures for on-line updating of minimum spanning trees}",
196 journal = "{SIAM Journal on Computing}",
203 author = "Martin Mare\v{s}",
204 title = "{Two linear time algorithms for MST on minor closed graph classes}",
205 journal = "{Archivum Mathematicum}",
211 @article{ ft:fibonacci,
212 author = {Michael L. Fredman and Robert Endre Tarjan},
213 title = {Fibonacci heaps and their uses in improved network optimization algorithms},
220 doi = {http://doi.acm.org/10.1145/28869.28874},
221 publisher = {ACM Press},
222 address = {New York, NY, USA},
225 @article{ komlos:verify,
226 author = {J{\'a}nos Koml{\'o}s},
227 title = {Linear verification for spanning trees.},
228 journal = {Combinatorica},
233 bibsource = {DBLP, http://dblp.uni-trier.de}
236 @inproceedings{ king:verify,
237 author = "Valerie King",
238 title = "A Simpler Minimum Spanning Tree Verification Algorithm",
239 booktitle = "Workshop on Algorithms and Data Structures",
242 url = "citeseer.ist.psu.edu/king95simpler.html" }
244 @article{ king:verifytwo,
245 title={{A Simpler Minimum Spanning Tree Verification Algorithm}},
246 author={King, Valerie},
247 journal={Algorithmica},
254 author = "Alexander Schrijver",
255 title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
256 series = "Algorithms and Combinatorics",
259 publisher = "Springer Verlag"
262 @inproceedings{ thorup:ac0,
263 author = {Mikkel Thorup},
264 title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
265 booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
267 isbn = {0-89871-538-5},
269 location = {Baltimore, Maryland},
270 publisher = {Society for Industrial and Applied Mathematics},
271 address = {Philadelphia, PA, USA},
274 @article{ kruskal:mst,
275 title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
276 author={Kruskal Jr, J.B.},
277 journal={Proceedings of the American Mathematical Society},
286 title={{Graph Theory}},
287 author={Diestel, R.},
289 publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K}
293 title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
295 journal={Proceedings of the thirty-fifth ACM symposium on Theory of computing},
298 publisher={ACM Press New York, NY, USA}
301 @article{ graham:msthistory,
302 title={{On the history of the minimum spanning tree problem}},
303 author={Graham, R.L. and Hell, P.},
304 journal={Annals of the History of Computing},
311 @article{ cayley:trees,
312 title={{A theorem on trees}},
313 author={Cayley, Arthur},
314 journal={Quart. J. Math},
320 @article{ dijkstra:mst,
321 title={{A note on two problems in connexion with graphs}},
322 author = "Dijkstra, E. W.",
323 journal={Numerische Mathematik},
332 author = "Prim, R. C.",
333 title = "Shortest connection networks and some generalizations",
334 journal = "Bell System Technical Journal",
340 @article{ choquet:mst,
341 title={{Etude de certains r{\'e}seaux de routes (in French)}},
342 author={Choquet, Gustave},
343 journal={Comptes-rendus de l'Académie des Sciences},
349 @incollection { sollin:mst,
350 title={{Le trace de canalisation (in French)}},
352 booktitle={Programming, Games, and Transportation Networks},
353 editor={Berge, C. and Ghouilla-Houri, A.},
354 publisher={Wiley, New York},
358 @article{ boyer:cutting,
359 title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
360 author={Boyer, J.M. and Myrvold, W.J.},
361 journal={Journal of Graph Algorithms and Applications},
368 @inproceedings{ takaoka:twothree,
369 title={{Theory of 2-3 Heaps}},
370 author={Takaoka, T. and Christchurch, N. Z.},
371 booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON'99},
372 location={Tokyo, Japan},
375 publisher={Springer},
376 series={{Lecture Notes in Computer Science}},
380 @inproceedings{ takaoka:trinomial,
381 title={{Theory of Trinomial Heaps}},
382 author={Takaoka, Tadao},
383 booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
384 location={Sydney, Australia},
387 publisher={Springer},
388 series={{Lecture Notes in Computer Science}},
393 title={{Introduction to Algorithms}},
394 author={Leiserson, C.E. and Rivest, R.L. and Cormen, T.H. and Stein, C.},
396 publisher={McGraw-Hill}
399 @inproceedings{ pettie:onlineverify,
400 author = "S. Pettie",
401 title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
402 tree verification problem",
403 booktitle = "Proc. 43rd Annual Symp. on the Foundations of Computer Science, Vancouver, Canada",
405 url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
408 @article{ dixon:verify,
409 author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
410 title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
411 journal = "SIAM J. Comput.",
416 url = "citeseer.ist.psu.edu/dixon92verification.html"
419 inproceedings{ pettie:minirand,
420 author = {Seth Pettie and Vijaya Ramachandran},
421 title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
422 booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms},
424 isbn = {0-89871-513-X},
426 location = {San Francisco, California},
427 publisher = {Society for Industrial and Applied Mathematics},
428 address = {Philadelphia, PA, USA}
431 @article{ buchsbaum:verify,
432 title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
433 author={Buchsbaum, A.L. and Kaplan, H. and Rogers, A. and Westbrook, J.R.},
434 journal={Proceedings of the thirtieth annual ACM symposium on Theory of computing},
437 publisher={ACM Press New York, NY, USA}
440 @article{ bacala:parametric,
441 title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
442 author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
443 journal={Theoretical Computer Science},
451 @inproceedings{ katriel:cycle,
452 author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
453 title = "A practical minimum spanning tree algorithm using the cycle property",
454 booktitle = "11th European Symposium on Algorithms(ESA)",
458 publisher = "Springer",
460 url = "citeseer.ist.psu.edu/katriel03practical.html"