1 @inproceedings{ bender:lca,
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 = "{A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees}",
189 @inproceedings { karger:sampling,
190 title={Random sampling in matroids, with applications to graph connectivity and minimum spanning trees},
191 author={Karger, D.R.},
192 booktitle={Proceedings of the 34th Annual Symposium on Foundations of Computer Science},
197 @article{ chan:backward,
198 title={{Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees}},
200 journal={Information Processing Letters},
208 @article { frederickson:online,
209 author = "Greg N. Frederickson",
210 title = "{Data structures for on-line updating of minimum spanning trees}",
211 journal = "{SIAM Journal on Computing}",
218 author = "Martin Mare\v{s}",
219 title = "{Two linear time algorithms for MST on minor closed graph classes}",
220 journal = "{Archivum Mathematicum}",
226 @inproceedings{ mm:rank,
227 author = "Martin Mare\v{s} and Milan Straka",
228 title = "Linear-Time Ranking of Permutations",
229 booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium",
230 location = "Eilat, Israel, October 8--10, 2007",
232 series = "Lecture Notes in Computer Science",
234 publisher = "Springer",
238 @article{ ft:fibonacci,
239 author = {Michael L. Fredman and Robert Endre Tarjan},
240 title = {Fibonacci heaps and their uses in improved network optimization algorithms},
247 doi = {http://doi.acm.org/10.1145/28869.28874},
248 publisher = {ACM Press},
249 address = {New York, NY, USA},
252 @article{ komlos:verify,
253 author = {J{\'a}nos Koml{\'o}s},
254 title = {Linear verification for spanning trees.},
255 journal = {Combinatorica},
260 bibsource = {DBLP, http://dblp.uni-trier.de}
263 @inproceedings{ king:verify,
264 author = "Valerie King",
265 title = "A Simpler Minimum Spanning Tree Verification Algorithm",
266 booktitle = "Workshop on Algorithms and Data Structures",
269 url = "citeseer.ist.psu.edu/king95simpler.html" }
271 @article{ king:verifytwo,
272 title={{A Simpler Minimum Spanning Tree Verification Algorithm}},
273 author={King, Valerie},
274 journal={Algorithmica},
281 author = "Alexander Schrijver",
282 title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
283 series = "Algorithms and Combinatorics",
286 publisher = "Springer Verlag"
289 @inproceedings{ thorup:aczero,
290 author = {Mikkel Thorup},
291 title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
292 booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
294 isbn = {0-89871-538-5},
296 location = {Baltimore, Maryland},
297 publisher = {Society for Industrial and Applied Mathematics},
298 address = {Philadelphia, PA, USA},
301 @article{ kruskal:mst,
302 title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
303 author={Kruskal Jr, J.B.},
304 journal={Proceedings of the American Mathematical Society},
313 title={{Graph Theory}},
314 author={Diestel, R.},
316 publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.}
319 @article{ graham:msthistory,
320 title={{On the history of the minimum spanning tree problem}},
321 author={Graham, R.L. and Hell, P.},
322 journal={Annals of the History of Computing},
329 @article{ cayley:trees,
330 title={{A theorem on trees}},
331 author={Cayley, Arthur},
332 journal={Quart. J. Math},
338 @article{ dijkstra:mst,
339 title={{A note on two problems in connexion with graphs}},
340 author = "Dijkstra, E. W.",
341 journal={Numerische Mathematik},
350 author = "Prim, R. C.",
351 title = "Shortest connection networks and some generalizations",
352 journal = "Bell System Technical Journal",
358 @article{ choquet:mst,
359 title={{Etude de certains r{\'e}seaux de routes}},
360 author={Choquet, Gustave},
361 journal={Comptes-rendus de l'Académie des Sciences},
368 @incollection { sollin:mst,
369 title={{Le trace de canalisation}},
371 booktitle={Programming, Games, and Transportation Networks},
372 editor={Berge, C. and Ghouilla-Houri, A.},
373 publisher={Wiley, New York},
378 @article{ boyer:cutting,
379 title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
380 author={Boyer, J.M. and Myrvold, W.J.},
381 journal={Journal of Graph Algorithms and Applications},
388 @inproceedings{ takaoka:twothree,
389 title={{Theory of 2-3 Heaps}},
390 author={Takaoka, T. and Christchurch, N. Z.},
391 booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON'99},
392 location={Tokyo, Japan},
395 publisher={Springer},
396 series={{Lecture Notes in Computer Science}},
400 @inproceedings{ takaoka:trinomial,
401 title={{Theory of Trinomial Heaps}},
402 author={Takaoka, Tadao},
403 booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
404 location={Sydney, Australia},
407 publisher={Springer},
408 series={{Lecture Notes in Computer Science}},
413 title={{Introduction to Algorithms}},
414 author={Leiserson, C.E. and Rivest, R.L. and Cormen, T.H. and Stein, C.},
416 publisher={McGraw-Hill}
419 @inproceedings{ pettie:onlineverify,
420 author = "S. Pettie",
421 title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
422 tree verification problem",
423 booktitle = "Proc. 43rd Annual Symp. on the Foundations of Computer Science, Vancouver, Canada",
425 url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
428 @article{ dixon:verify,
429 author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
430 title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
431 journal = "SIAM J. Comput.",
436 url = "citeseer.ist.psu.edu/dixon92verification.html"
439 inproceedings{ pettie:minirand,
440 author = {Seth Pettie and Vijaya Ramachandran},
441 title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
442 booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms},
444 isbn = {0-89871-513-X},
446 location = {San Francisco, California},
447 publisher = {Society for Industrial and Applied Mathematics},
448 address = {Philadelphia, PA, USA}
451 @article{ buchsbaum:verify,
452 title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
453 author={Buchsbaum, A.L. and Kaplan, H. and Rogers, A. and Westbrook, J.R.},
454 journal={Proceedings of the thirtieth annual ACM Symposium on Theory of Computing},
457 publisher={ACM Press New York, NY, USA}
460 @article{ bacala:parametric,
461 title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
462 author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
463 journal={Theoretical Computer Science},
471 @inproceedings{ katriel:cycle,
472 author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
473 title = "A practical minimum spanning tree algorithm using the cycle property",
474 booktitle = "11th European Symposium on Algorithms (ESA)",
478 publisher = "Springer",
480 url = "citeseer.ist.psu.edu/katriel03practical.html"
483 @article{ alstrup:nca,
484 title={{Nearest common ancestors: a survey and a new distributed algorithm}},
485 author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
486 journal={Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures},
489 publisher={ACM Press New York, NY, USA}
493 title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
494 author={Gabow, H.N. and Galil, Z. and Spencer, T. and Tarjan, R.E.},
495 journal={Combinatorica},
503 @Unpublished{ eisner:tutorial,
504 author = {Jason Eisner},
505 title = {State-of-the-Art Algorithms for Minimum Spanning
506 Trees: A Tutorial Discussion},
507 note = {Manuscript available online (78 pages), University of Pennsylvania},
509 url = {http://cs.jhu.edu/~jason/papers/#ms97},
513 title={{On finding lowest common ancestors in trees.}},
514 author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
515 journal={SIAM Journal on Computing},
521 @book{ knuth:fundalg,
522 author = {Donald E. Knuth},
523 title = {The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms},
525 isbn = {0-201-89683-4},
526 publisher = {Addison Wesley Longman Publishing Co., Inc.},
527 address = {Redwood City, CA, USA},
530 @book{ knuth:seminalg,
531 author = {Donald E. Knuth},
532 title = {The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical algorithms},
534 isbn = {978-0-201-89684-8},
535 publisher = {Addison Wesley Longman Publishing Co., Inc.},
536 address = {Redwood City, CA, USA},
540 author = {Donald E. Knuth},
541 title = {{The Art of Computer Programming, Volume 3 (2nd ed.): Sorting and Searching}},
543 isbn = {978-0-201-89685-5},
544 publisher = {Addison Wesley Longman Publishing Co., Inc.},
545 address = {Redwood City, CA, USA},
548 @inproceedings{ hagerup:wordram,
549 author = {Torben Hagerup},
550 title = {{Sorting and Searching on the Word RAM}},
551 booktitle = {STACS '98: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science},
553 isbn = {3-540-64230-7},
555 publisher = {Springer-Verlag},
556 address = {London, UK},
559 @inproceedings{ cook:ram,
560 author = {Stephen A. Cook and Robert A. Reckhow},
561 title = {Time-bounded random access machines},
562 booktitle = {STOC '72: Proceedings of the fourth annual ACM Symposium on Theory of Computing},
565 location = {Denver, Colorado, United States},
566 doi = {http://doi.acm.org/10.1145/800152.804898},
568 address = {New York, NY, USA},
571 @book{ okasaki:funcds,
572 author = {Chris Okasaki},
573 title = {Purely Functional Data Structures},
575 publisher = {Cambridge University Press}
578 @book { intel:pentium,
579 author = {{Intel Corp.}},
580 title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference},
582 publisher = {Intel Corp.},
583 xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
586 @article{ hagerup:dd,
587 title={{Deterministic Dictionaries}},
588 author={Hagerup, T. and Miltersen, P.B. and Pagh, R.},
589 journal={J. Algorithms},
596 @article{ fredman:sst,
597 title={{Storing a Sparse Table with $\O(1)$ Worst Case Access Time}},
598 author={Fredman, M.L. and Koml{\'o}s, J. and Szemer{\'e}di, E.},
599 journal={Journal of the ACM (JACM)},
604 publisher={ACM Press New York, NY, USA}
607 @book{ motwani:randalg,
608 title={{Randomized Algorithms}},
609 author={Motwani, R. and Raghavan, P.},
611 publisher={Cambridge University Press}
615 title={{Surpassing the information theoretic bound with fusion trees}},
616 author={Fredman, M.L. and Willard, D.E.},
617 journal={Journal of Computer and System Sciences},
622 publisher={Academic Press, Inc. Orlando, FL, USA}
625 @article{ han:detsort,
626 title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}},
628 journal={Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing},
631 publisher={ACM Press New York, NY, USA}
634 @article{ hanthor:randsort,
635 title={{Integer Sorting in $\O(n\sqrt{\log\log n})$ Expected Time and Linear Space}},
636 author={Han, Y. and Thorup, M.},
637 journal={Proceedings of the 43rd Symposium on Foundations of Computer Science},
640 publisher={IEEE Computer Society Washington, DC, USA}
643 @article{ ito:newrap,
644 title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}},
645 author={Ito, M. and Takagi, N. and Yajima, S.},
646 journal={Proc. 12th IEEE Symp. Computer Arithmetic},
651 @article{ brodnik:lsb,
652 title={{Computation of the least significant set bit}},
653 author={Brodnik, A.},
654 journal={Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia},
658 @article{ turan:succinct,
659 title={{Succinct representation of graphs.}},
660 author={Tur\'an, G.},
661 journal={Discrete Applied Mathematics},
668 @book{ jones:haskell,
669 title={{Haskell 98 Language and Libraries: The Revised Report}},
670 author={Jones, P. and Simon, L.},
672 publisher={Cambridge University Press}
675 @article{ mader:dens,
676 title={{Homomorphieeigenschaften und mittlere Kantendichte von Graphen}},
678 journal={Mathematische Annalen},
683 publisher={Springer},
687 @inproceedings{ gustedt:parallel,
688 author = "Jens Gustedt",
689 title = "Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel",
690 booktitle = "Symposium on Theoretical Aspects of Computer Science",
693 url = "citeseer.ist.psu.edu/223918.html"
696 @article{ myrvold:rank,
697 title={{Ranking and unranking permutations in linear time}},
698 author={Myrvold, W.J. and Ruskey, F.},
699 journal={Information Processing Letters},
706 @inproceedings{ critani:rau,
707 title={{Ranking and unranking permutations with applications}},
708 author={Critani, F. and Dall'Aglio, M. and Di Biase, G.},
709 booktitle={Innovation in Mathematics: Proceedings of Second International Mathematica Symposium},
714 @article{ ruskey:ham,
715 title={{The Hamiltonicity of directed-Cayley graphs (or: A tale of backtracking)}},
716 author={Ruskey, F. and Jiang, M. and Weston, A.},
717 journal={Discrete Appl. Math},
723 @article{ ruskey:hce,
724 title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn}},
725 author={Ruskey, F. and Savage, C.D.},
726 journal={SIAM Journal on Discrete Mathematics},
733 @article{ liehe:raulow,
734 title={{Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis}},
735 author={Liebehenschel, J.},
736 journal={Journal of Automata, Languages and Combinatorics},
743 @book{ reingold:catp,
744 title={{Combinatorial Algorithms: Theory and Practice}},
745 author={Reingold, E.M.},
747 publisher={Prentice Hall College Div}
750 @inproceedings{ dietz:oal,
751 author = {Paul F. Dietz},
752 title = {Optimal Algorithms for List Indexing and Subset Rank},
753 booktitle = {WADS '89: Proceedings of the Workshop on Algorithms and Data Structures},
755 isbn = {3-540-51542-9},
757 publisher = {Springer-Verlag},
758 address = {London, UK},
762 title={{The 15 Puzzle Book}},
763 author={Slocum, J. and Sonneveld D.},
765 publisher={The Slocum Puzzle Foundation, Beverly Hills, CA, USA}
769 title={{Graph minors: XX. Wagner's Conjecture}},
770 author={Robertson, N. and Seymour, P. D.},
771 journal={Journal of Combinatorial Theory Series B},
776 publisher={Academic Press, Inc. Orlando, FL, USA}
780 title={{Invitation to Discrete Mathematics}},
781 author={Matou{\v{s}}ek, J. and Ne{\v{s}}et{\v{r}}il, J.},
783 publisher={Oxford University Press}
786 @article{ stanley:econe,
787 title={{Enumerative combinatorics. Vol. 1}},
788 author={Stanley, R.P.},
789 journal={Cambridge Studies in Advanced Mathematics},
794 @article{ kaplansky:rooks,
795 title={{The problem of the rooks and its applications}},
796 author={Kaplansky, I. and Riordan, J.},
797 journal={Duke Math. J},
804 @article{ dinic:flow,
805 author = {E. A. Dinic},
806 title = {Algorithm for solution of a problem of maximum flow in networks with power estimation},
807 journal = {Soviet Math. Dokl.},
813 @article{ even:dinic,
814 author = {Shimon Even and Robert Endre Tarjan},
815 title = {Network Flow and Testing Graph Connectivity},
818 journal = {SIAM Journal on Computing},
822 url = {http://link.aip.org/link/?SMJ/4/507/1},
823 doi = {10.1137/0204043}
826 @article{ valiant:permanent,
827 title={{The complexity of computing the permanent}},
828 author={Valiant, L. G.},
829 journal={Theoretical Computer Science},
836 @article{ jerrum:permanent,
837 title={{A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries}},
838 author={Jerrum, M. and Sinclair, A. and Vigoda, E.},
839 journal={Journal of the ACM},
846 @article{ kasteleyn:crystals,
847 title={{Graph theory and crystal physics}},
848 author={Kasteleyn, P. W.},
849 journal={Graph Theory and Theoretical Physics},
850 publisher={Academic Press, London},
855 @article{ yuster:matching,
856 title={{Maximum matching in graphs with an excluded minor}},
857 author={Yuster, R. and Zwick, U.},
858 journal={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
861 publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
864 @article{ mucha:matching,
865 title={{Maximum Matchings in Planar Graphs via Gaussian Elimination}},
866 author={Mucha, M. and Sankowski, P.},
867 journal={Algorithmica},
875 @article {lovasz:minors,
876 title={{Graph Minor Theory}},
877 author={Lov\'asz, L.},
878 journal={Bulletin of the American Mathematical Society},
885 @article{ andersson:fusion,
886 title={{Fusion trees can be implemented with AC0 instructions only}},
887 author={Andersson, A. and Miltersen, P.B. and Thorup, M.},
888 journal={Theoretical Computer Science},
896 @article{ thorup:rampq,
897 title={{On RAM priority queues}},
899 journal={SIAM journal on computing(Print)},
904 publisher={Society for Industrial and Applied Mathematics}
907 @article{ thorup:pqsssp,
908 title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
910 journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
913 publisher={ACM Press New York, NY, USA}
916 @article{ chazelle:mstapprox,
917 title={{Approximating the Minimum Spanning Tree Weight in Sublinear Time}},
918 author={Chazelle, B. and Rubinfeld, R. and Trevisan, L.},
919 journal={SIAM Journal on Computing},
926 @inproceedings{ czumaj:metric,
927 author = {Artur Czumaj and Christian Sohler},
928 title = {Estimating the weight of metric minimum spanning trees in sublinear-time},
929 booktitle = {STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},
931 isbn = {1-58113-852-0},
933 location = {Chicago, IL, USA},
934 doi = {http://doi.acm.org/10.1145/1007352.1007386},
936 address = {New York, NY, USA},
939 @inproceedings{ czumaj:euclidean,
940 author = {Artur Czumaj and Funda Erg\"{u}n and Lance Fortnow and Avner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler},
941 title = {Sublinear-time approximation of Euclidean minimum spanning tree},
942 booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
944 isbn = {0-89871-538-5},
946 location = {Baltimore, Maryland},
947 publisher = {Society for Industrial and Applied Mathematics},
948 address = {Philadelphia, PA, USA},
953 title = {IEEE Standard 754-1985 for Binary Floating-point Arithmetic},
958 @article{ dgoldberg:fp,
959 title={{What every computer scientist should know about floating-point arithmetic}},
960 author={Goldberg, D.},
961 journal={ACM Computing Surveys (CSUR)},
966 publisher={ACM Press New York, NY, USA}
969 @article{ thorup:floatint,
970 title={{Floats, Integers, and Single Source Shortest Paths}},
972 journal={Journal of Algorithms},
977 publisher={Academic Press}
980 @article{ shamos:closest,
981 title={{Closest-point problems}},
982 author={Shamos, M. I. and Hoey, D.},
983 journal={Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science},
988 @article{ fortune:voronoi,
989 title={{A sweepline algorithm for Voronoi diagrams}},
990 author={Fortune, S.},
991 journal={Algorithmica},
999 @article{ zhou:nodel,
1000 title={{Efficient minimum spanning tree construction without Delaunay triangulation}},
1001 author={Zhou, H. and Shenoy, N. and Nicholls, W.},
1002 journal={Information Processing Letters},
1007 publisher={Elsevier}
1010 @techreport{ eppstein:spanning,
1011 title={{Spanning Trees and Spanners}},
1012 author={Eppstein, D.},
1014 institution={Information and Computer Science, University of California, Irvine}
1017 @article{ garey:steiner,
1018 title={{The Complexity of Computing Steiner Minimal Trees}},
1019 author={Garey, M.R. and Graham, R.L. and Johnson, D.S.},
1020 journal={SIAM Journal on Applied Mathematics},
1027 @article{ garey:rectisteiner,
1028 title={{The Rectilinear Steiner Tree Problem is NP-Complete}},
1029 author={Garey, M.R. and Johnson, D.S.},
1030 journal={SIAM Journal on Applied Mathematics},
1037 @article{ proemel:steiner,
1038 title={{A new approximation algorithm for the Steiner tree problem with performance ratio $5/3$}},
1039 author={Promel, H.J. and Steger, A.},
1040 journal={Journal of Algorithms},
1046 @article{ arora:tspapx,
1047 title={{Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems}},
1049 journal={Journal of the ACM (JACM)},
1054 publisher={ACM Press New York, NY, USA}
1057 @article{ harel:nca,
1058 title={{Fast algorithms for finding nearest common ancestors}},
1059 author={Harel, D. and Tarjan, R.E.},
1060 journal={SIAM Journal on Computing},
1065 publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
1069 author = "R. E. Gomory and T. C. Hu",
1070 title = "Multi-Terminal Network Flows",
1071 journal = "{Journal of SIAM}",
1078 @inproceedings{ bhalgat:ght,
1079 author = {Ramesh Hariharan and Telikepalli Kavitha and Debmalya Panigrahi and Anand Bhalgat},
1080 title = {{An $\widehat\O(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs}},
1081 booktitle = {STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing},
1083 isbn = {978-1-59593-631-8},
1085 location = {San Diego, California, USA},
1086 doi = {http://doi.acm.org/10.1145/1250790.1250879},
1088 address = {New York, NY, USA},
1091 @article{ sleator:trees,
1092 title={{A data structure for dynamic trees}},
1093 author={Sleator, D.D. and Tarjan, R.E.},
1094 journal={Journal of Computer and System Sciences},
1099 publisher={Academic Press, Inc. Orlando, FL, USA}