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 { fw90trans,
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" }
245 author = "Alexander Schrijver",
246 title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
247 series = "Algorithms and Combinatorics",
250 publisher = "Springer Verlag"
253 @inproceedings{ thorup:ac0,
254 author = {Mikkel Thorup},
255 title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
256 booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
258 isbn = {0-89871-538-5},
260 location = {Baltimore, Maryland},
261 publisher = {Society for Industrial and Applied Mathematics},
262 address = {Philadelphia, PA, USA},
265 @article{ kruskal:mst,
266 title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
267 author={Kruskal Jr, J.B.},
268 journal={Proceedings of the American Mathematical Society},
277 title={{Graph Theory}},
278 author={Diestel, R.},
280 publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K}
284 title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
286 journal={Proceedings of the thirty-fifth ACM symposium on Theory of computing},
289 publisher={ACM Press New York, NY, USA}
292 @article{ graham:msthistory,
293 title={{On the history of the minimum spanning tree problem}},
294 author={Graham, R.L. and Hell, P.},
295 journal={Annals of the History of Computing},
302 @article{ cayley:trees,
303 title={{A theorem on trees}},
304 author={Cayley, Arthur},
305 journal={Quart. J. Math},
311 @article{ dijkstra:mst,
312 title={{A note on two problems in connexion with graphs}},
313 author = "Dijkstra, E. W.",
314 journal={Numerische Mathematik},
323 author = "Prim, R. C.",
324 title = "Shortest connection networks and some generalizations",
325 journal = "Bell System Technical Journal",
331 @article{ choquet:mst,
332 title={{Etude de certains r{\'e}seaux de routes (in French)}},
333 author={Choquet, Gustave},
334 journal={Comptes-rendus de l'Académie des Sciences},
340 @incollection { sollin:mst,
341 title={{Le trace de canalisation (in French)}},
343 booktitle={Programming, Games, and Transportation Networks},
344 editor={Berge, C. and Ghouilla-Houri, A.},
345 publisher={Wiley, New York},
349 @article{ boyer:cutting,
350 title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
351 author={Boyer, J.M. and Myrvold, W.J.},
352 journal={Journal of Graph Algorithms and Applications},