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{ chazelle:almostacker,
79 title={{A faster deterministic algorithm for minimum spanning trees}},
80 author={Chazelle, B.},
81 journal={Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS'97)},
84 publisher={IEEE Computer Society Washington, DC, USA}
87 @article{ nesetril:history,
88 author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
89 title = "{Some remarks on the history of MST-problem}",
90 journal = "Archivum Mathematicum",
96 @article{ nesetril:boruvka,
97 author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
98 title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
99 journal = "Discrete Mathematics",
100 volume = "233(1--3)",
105 @incollection { nesetril:minors,
106 author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
107 title = "{Colorings and Homomorphisms of Minor Closed Classes}",
108 booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
109 editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
112 publisher = "Springer Verlag"
115 @article { boruvka:ojistem,
116 author = "Otakar Bor{\accent23u}vka",
117 title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
118 journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
122 note = "In Czech with German summary"
125 @article { boruvka:networks,
126 author = "Otakar Bor{\accent23u}vka",
127 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)}",
128 journal = "Elektronick\'y obzor",
135 @article { jarnik:ojistem,
136 author = "Vojt\v{e}ch Jarn\'\i{}k",
137 title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
138 journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
146 author = "Robert E. Tarjan",
147 title = "{Data structures and network algorithms}",
148 series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}",
154 @article { gh:history,
155 author = "R. L. Graham and P. Hell",
156 title = "{On the history of the minimum spanning tree problem}",
157 journal = "{Annals of the History of Computing}",
163 @techreport { pettie:ackermann,
164 author = "Seth Pettie",
165 title = "{Finding minimum spanning trees in $\O(m\alpha(m,n))$ time}",
166 institution = "Univ. of Texas at Austin",
172 @article{ pettie:optimal,
173 author = {Seth Pettie and Vijaya Ramachandran},
174 title= {An optimal minimum spanning tree algorithm},
175 journal = {Journal of the {ACM}},
182 @inproceedings { pettie:optimal-conf,
183 author = "Seth Pettie and Vijaya Ramachandran",
184 title = "{An Optimal Minimum Spanning Tree Algorithm}",
185 booktitle = "{Proceedings of ICALP'2000}",
187 publisher = "Springer Verlag",
191 @article { pettie:alpha,
192 title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}},
195 publisher={University of Texas at Austin Austin, TX, USA}
198 @article { karger:randomized,
199 author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
200 title = "{A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees}",
208 @inproceedings { karger:sampling,
209 title={Random sampling in matroids, with applications to graph connectivity and minimum spanning trees},
210 author={Karger, D.R.},
211 booktitle={Proceedings of the 34th Annual Symposium on Foundations of Computer Science},
216 @article{ chan:backward,
217 title={{Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees}},
219 journal={Information Processing Letters},
227 @article { frederickson:online,
228 author = "Greg N. Frederickson",
229 title = "{Data structures for on-line updating of minimum spanning trees}",
230 journal = "{SIAM Journal on Computing}",
237 author = "Martin Mare\v{s}",
238 title = "{Two linear time algorithms for MST on minor closed graph classes}",
239 journal = "{Archivum Mathematicum}",
245 @inproceedings{ mm:rank,
246 author = "Martin Mare\v{s} and Milan Straka",
247 title = "Linear-Time Ranking of Permutations",
248 booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium",
249 location = "Eilat, Israel, October 8--10, 2007",
251 series = "Lecture Notes in Computer Science",
253 publisher = "Springer",
257 @article{ ft:fibonacci,
258 author = {Michael L. Fredman and Robert Endre Tarjan},
259 title = {Fibonacci heaps and their uses in improved network optimization algorithms},
266 doi = {http://doi.acm.org/10.1145/28869.28874},
267 publisher = {ACM Press},
268 address = {New York, NY, USA},
271 @article{ komlos:verify,
272 author = {J{\'a}nos Koml{\'o}s},
273 title = {Linear verification for spanning trees.},
274 journal = {Combinatorica},
279 bibsource = {DBLP, http://dblp.uni-trier.de}
282 @inproceedings{ king:verify,
283 author = "Valerie King",
284 title = "A Simpler Minimum Spanning Tree Verification Algorithm",
285 booktitle = "Workshop on Algorithms and Data Structures",
288 url = "citeseer.ist.psu.edu/king95simpler.html" }
290 @article{ king:verifytwo,
291 title={{A Simpler Minimum Spanning Tree Verification Algorithm}},
292 author={King, Valerie},
293 journal={Algorithmica},
300 author = "Alexander Schrijver",
301 title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
302 series = "Algorithms and Combinatorics",
305 publisher = "Springer Verlag"
308 @inproceedings{ thorup:aczero,
309 author = {Mikkel Thorup},
310 title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
311 booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
313 isbn = {0-89871-538-5},
315 location = {Baltimore, Maryland},
316 publisher = {Society for Industrial and Applied Mathematics},
317 address = {Philadelphia, PA, USA},
320 @article{ kruskal:mst,
321 title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
322 author={Kruskal Jr, J.B.},
323 journal={Proceedings of the American Mathematical Society},
332 title={{Graph Theory}},
333 author={Diestel, R.},
335 publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.}
338 @article{ graham:msthistory,
339 title={{On the history of the minimum spanning tree problem}},
340 author={Graham, R.L. and Hell, P.},
341 journal={Annals of the History of Computing},
348 @article{ cayley:trees,
349 title={{A theorem on trees}},
350 author={Cayley, Arthur},
351 journal={Quart. J. Math},
357 @article{ dijkstra:mst,
358 title={{A note on two problems in connexion with graphs}},
359 author = "Dijkstra, E. W.",
360 journal={Numerische Mathematik},
369 author = "Prim, R. C.",
370 title = "Shortest connection networks and some generalizations",
371 journal = "Bell System Technical Journal",
377 @article{ choquet:mst,
378 title={{Etude de certains r{\'e}seaux de routes}},
379 author={Choquet, Gustave},
380 journal={Comptes-rendus de l'Académie des Sciences},
387 @incollection { sollin:mst,
388 title={{Le trace de canalisation}},
390 booktitle={Programming, Games, and Transportation Networks},
391 editor={Berge, C. and Ghouilla-Houri, A.},
392 publisher={Wiley, New York},
397 @article{ boyer:cutting,
398 title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
399 author={Boyer, J.M. and Myrvold, W.J.},
400 journal={Journal of Graph Algorithms and Applications},
407 @inproceedings{ takaoka:twothree,
408 title={{Theory of 2-3 Heaps}},
409 author={Takaoka, T. and Christchurch, N. Z.},
410 booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON'99},
411 location={Tokyo, Japan},
414 publisher={Springer},
415 series={{Lecture Notes in Computer Science}},
419 @inproceedings{ takaoka:trinomial,
420 title={{Theory of Trinomial Heaps}},
421 author={Takaoka, Tadao},
422 booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
423 location={Sydney, Australia},
426 publisher={Springer},
427 series={{Lecture Notes in Computer Science}},
432 title={{Introduction to Algorithms}},
433 author={Leiserson, C.E. and Rivest, R.L. and Cormen, T.H. and Stein, C.},
435 publisher={McGraw-Hill}
438 @article{ pettie:onlineverify,
439 author = {Seth Pettie},
440 title = {An Inverse-{A}ckermann Type Lower Bound for Online
441 Minimum Spanning Tree Verification},
442 journal = {Combinatorica},
449 @inproceedings{ pettie:onlineverify-conf,
450 author = "S. Pettie",
451 title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
452 tree verification problem",
453 booktitle = "Proc. 43rd Annual Symp. on the Foundations of Computer Science, Vancouver, Canada",
455 url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
458 @article{ dixon:verify,
459 author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
460 title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
461 journal = "SIAM J. Comput.",
466 url = "citeseer.ist.psu.edu/dixon92verification.html"
469 @inproceedings{ pettie:minirand,
470 author = {Seth Pettie and Vijaya Ramachandran},
471 title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
472 booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms},
474 isbn = {0-89871-513-X},
476 location = {San Francisco, California},
477 publisher = {Society for Industrial and Applied Mathematics},
478 address = {Philadelphia, PA, USA}
481 @article{ buchsbaum:verify,
482 title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
483 author={Buchsbaum, A.L. and Kaplan, H. and Rogers, A. and Westbrook, J.R.},
484 journal={Proceedings of the thirtieth annual ACM Symposium on Theory of Computing},
487 publisher={ACM Press New York, NY, USA}
490 @article{ bacala:parametric,
491 title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
492 author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
493 journal={Theoretical Computer Science},
501 @inproceedings{ katriel:cycle,
502 author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
503 title = "A practical minimum spanning tree algorithm using the cycle property",
504 booktitle = "11th European Symposium on Algorithms (ESA)",
508 publisher = "Springer",
510 url = "citeseer.ist.psu.edu/katriel03practical.html"
513 @article{ alstrup:nca,
514 title={{Nearest common ancestors: a survey and a new distributed algorithm}},
515 author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
516 journal={Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures},
519 publisher={ACM Press New York, NY, USA}
523 title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
524 author={Gabow, H.N. and Galil, Z. and Spencer, T. and Tarjan, R.E.},
525 journal={Combinatorica},
533 @Unpublished{ eisner:tutorial,
534 author = {Jason Eisner},
535 title = {State-of-the-Art Algorithms for Minimum Spanning
536 Trees: A Tutorial Discussion},
537 note = {Manuscript available online (78 pages), University of Pennsylvania},
539 url = {http://cs.jhu.edu/~jason/papers/#ms97},
543 title={{On finding lowest common ancestors in trees.}},
544 author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
545 journal={SIAM Journal on Computing},
551 @book{ knuth:fundalg,
552 author = {Donald E. Knuth},
553 title = {The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms},
555 isbn = {0-201-89683-4},
556 publisher = {Addison Wesley Longman Publishing Co., Inc.},
557 address = {Redwood City, CA, USA},
560 @book{ knuth:seminalg,
561 author = {Donald E. Knuth},
562 title = {The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical algorithms},
564 isbn = {978-0-201-89684-8},
565 publisher = {Addison Wesley Longman Publishing Co., Inc.},
566 address = {Redwood City, CA, USA},
570 author = {Donald E. Knuth},
571 title = {{The Art of Computer Programming, Volume 3 (2nd ed.): Sorting and Searching}},
573 isbn = {978-0-201-89685-5},
574 publisher = {Addison Wesley Longman Publishing Co., Inc.},
575 address = {Redwood City, CA, USA},
578 @inproceedings{ hagerup:wordram,
579 author = {Torben Hagerup},
580 title = {{Sorting and Searching on the Word RAM}},
581 booktitle = {STACS '98: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science},
583 isbn = {3-540-64230-7},
585 publisher = {Springer-Verlag},
586 address = {London, UK},
589 @inproceedings{ cook:ram,
590 author = {Stephen A. Cook and Robert A. Reckhow},
591 title = {Time-bounded random access machines},
592 booktitle = {STOC '72: Proceedings of the fourth annual ACM Symposium on Theory of Computing},
595 location = {Denver, Colorado, United States},
596 doi = {http://doi.acm.org/10.1145/800152.804898},
598 address = {New York, NY, USA},
601 @book{ okasaki:funcds,
602 author = {Chris Okasaki},
603 title = {Purely Functional Data Structures},
605 publisher = {Cambridge University Press}
608 @book { intel:pentium,
609 author = {{Intel Corp.}},
610 title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference},
612 publisher = {Intel Corp.},
613 xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
616 @article{ hagerup:dd,
617 title={{Deterministic Dictionaries}},
618 author={Hagerup, T. and Miltersen, P.B. and Pagh, R.},
619 journal={J. Algorithms},
626 @article{ fredman:sst,
627 title={{Storing a Sparse Table with $\O(1)$ Worst Case Access Time}},
628 author={Fredman, M.L. and Koml{\'o}s, J. and Szemer{\'e}di, E.},
629 journal={Journal of the ACM (JACM)},
634 publisher={ACM Press New York, NY, USA}
637 @book{ motwani:randalg,
638 title={{Randomized Algorithms}},
639 author={Motwani, R. and Raghavan, P.},
641 publisher={Cambridge University Press}
645 title={{Surpassing the information theoretic bound with fusion trees}},
646 author={Fredman, M.L. and Willard, D.E.},
647 journal={Journal of Computer and System Sciences},
652 publisher={Academic Press, Inc. Orlando, FL, USA}
655 @article{ han:detsort,
656 title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}},
658 journal={Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing},
661 publisher={ACM Press New York, NY, USA}
664 @article{ hanthor:randsort,
665 title={{Integer Sorting in $\O(n\sqrt{\log\log n})$ Expected Time and Linear Space}},
666 author={Han, Y. and Thorup, M.},
667 journal={Proceedings of the 43rd Symposium on Foundations of Computer Science},
670 publisher={IEEE Computer Society Washington, DC, USA}
673 @article{ ito:newrap,
674 title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}},
675 author={Ito, M. and Takagi, N. and Yajima, S.},
676 journal={Proc. 12th IEEE Symp. Computer Arithmetic},
681 @article{ brodnik:lsb,
682 title={{Computation of the least significant set bit}},
683 author={Brodnik, A.},
684 journal={Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia},
688 @article{ turan:succinct,
689 title={{Succinct representation of graphs.}},
690 author={Tur\'an, G.},
691 journal={Discrete Applied Mathematics},
698 @book{ jones:haskell,
699 title={{Haskell 98 Language and Libraries: The Revised Report}},
700 author={Jones, P. and Simon, L.},
702 publisher={Cambridge University Press}
705 @article{ mader:dens,
706 title={{Homomorphieeigenschaften und mittlere Kantendichte von Graphen}},
708 journal={Mathematische Annalen},
713 publisher={Springer},
717 @inproceedings{ gustedt:parallel,
718 author = "Jens Gustedt",
719 title = "Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel",
720 booktitle = "Symposium on Theoretical Aspects of Computer Science",
723 url = "citeseer.ist.psu.edu/223918.html"
726 @article{ myrvold:rank,
727 title={{Ranking and unranking permutations in linear time}},
728 author={Myrvold, W.J. and Ruskey, F.},
729 journal={Information Processing Letters},
736 @inproceedings{ critani:rau,
737 title={{Ranking and unranking permutations with applications}},
738 author={Critani, F. and Dall'Aglio, M. and Di Biase, G.},
739 booktitle={Innovation in Mathematics: Proceedings of Second International Mathematica Symposium},
744 @article{ ruskey:ham,
745 title={{The Hamiltonicity of directed-Cayley graphs (or: A tale of backtracking)}},
746 author={Ruskey, F. and Jiang, M. and Weston, A.},
747 journal={Discrete Appl. Math},
753 @article{ ruskey:hce,
754 title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn}},
755 author={Ruskey, F. and Savage, C.D.},
756 journal={SIAM Journal on Discrete Mathematics},
763 @article{ liehe:raulow,
764 title={{Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis}},
765 author={Liebehenschel, J.},
766 journal={Journal of Automata, Languages and Combinatorics},
773 @book{ reingold:catp,
774 title={{Combinatorial Algorithms: Theory and Practice}},
775 author={Reingold, E.M.},
777 publisher={Prentice Hall College Div}
780 @inproceedings{ dietz:oal,
781 author = {Paul F. Dietz},
782 title = {Optimal Algorithms for List Indexing and Subset Rank},
783 booktitle = {WADS '89: Proceedings of the Workshop on Algorithms and Data Structures},
785 isbn = {3-540-51542-9},
787 publisher = {Springer-Verlag},
788 address = {London, UK},
792 title={{The 15 Puzzle Book}},
793 author={Slocum, J. and Sonneveld D.},
795 publisher={The Slocum Puzzle Foundation, Beverly Hills, CA, USA}
799 title={{Graph minors: XX. Wagner's Conjecture}},
800 author={Robertson, N. and Seymour, P. D.},
801 journal={Journal of Combinatorial Theory Series B},
806 publisher={Academic Press, Inc. Orlando, FL, USA}
810 title={{Invitation to Discrete Mathematics}},
811 author={Matou{\v{s}}ek, J. and Ne{\v{s}}et{\v{r}}il, J.},
813 publisher={Oxford University Press}
816 @article{ stanley:econe,
817 title={{Enumerative combinatorics. Vol. 1}},
818 author={Stanley, R.P.},
819 journal={Cambridge Studies in Advanced Mathematics},
824 @article{ kaplansky:rooks,
825 title={{The problem of the rooks and its applications}},
826 author={Kaplansky, I. and Riordan, J.},
827 journal={Duke Math. J},
834 @article{ dinic:flow,
835 author = {E. A. Dinic},
836 title = {Algorithm for solution of a problem of maximum flow in networks with power estimation},
837 journal = {Soviet Math. Dokl.},
843 @article{ even:dinic,
844 author = {Shimon Even and Robert Endre Tarjan},
845 title = {Network Flow and Testing Graph Connectivity},
848 journal = {SIAM Journal on Computing},
852 url = {http://link.aip.org/link/?SMJ/4/507/1},
853 doi = {10.1137/0204043}
856 @article{ valiant:permanent,
857 title={{The complexity of computing the permanent}},
858 author={Valiant, L. G.},
859 journal={Theoretical Computer Science},
866 @article{ jerrum:permanent,
867 title={{A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries}},
868 author={Jerrum, M. and Sinclair, A. and Vigoda, E.},
869 journal={Journal of the ACM},
876 @article{ kasteleyn:crystals,
877 title={{Graph theory and crystal physics}},
878 author={Kasteleyn, P. W.},
879 journal={Graph Theory and Theoretical Physics},
880 publisher={Academic Press, London},
885 @article{ yuster:matching,
886 title={{Maximum matching in graphs with an excluded minor}},
887 author={Yuster, R. and Zwick, U.},
888 journal={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
891 publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
894 @article{ mucha:matching,
895 title={{Maximum Matchings in Planar Graphs via Gaussian Elimination}},
896 author={Mucha, M. and Sankowski, P.},
897 journal={Algorithmica},
905 @article {lovasz:minors,
906 title={{Graph Minor Theory}},
907 author={Lov\'asz, L.},
908 journal={Bulletin of the American Mathematical Society},
915 @article{ andersson:fusion,
916 title={{Fusion trees can be implemented with AC0 instructions only}},
917 author={Andersson, A. and Miltersen, P.B. and Thorup, M.},
918 journal={Theoretical Computer Science},
926 @article{ thorup:rampq,
927 title={{On RAM priority queues}},
929 journal={SIAM journal on computing(Print)},
934 publisher={Society for Industrial and Applied Mathematics}
937 @article{ thorup:pqsssp,
938 title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
940 journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
943 publisher={ACM Press New York, NY, USA}
946 @article{ chazelle:mstapprox,
947 title={{Approximating the Minimum Spanning Tree Weight in Sublinear Time}},
948 author={Chazelle, B. and Rubinfeld, R. and Trevisan, L.},
949 journal={SIAM Journal on Computing},
956 @inproceedings{ czumaj:metric,
957 author = {Artur Czumaj and Christian Sohler},
958 title = {Estimating the weight of metric minimum spanning trees in sublinear-time},
959 booktitle = {STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},
961 isbn = {1-58113-852-0},
963 location = {Chicago, IL, USA},
964 doi = {http://doi.acm.org/10.1145/1007352.1007386},
966 address = {New York, NY, USA},
969 @inproceedings{ czumaj:euclidean,
970 author = {Artur Czumaj and Funda Erg\"{u}n and Lance Fortnow and Avner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler},
971 title = {Sublinear-time approximation of Euclidean minimum spanning tree},
972 booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
974 isbn = {0-89871-538-5},
976 location = {Baltimore, Maryland},
977 publisher = {Society for Industrial and Applied Mathematics},
978 address = {Philadelphia, PA, USA},
983 title = {IEEE Standard 754-1985 for Binary Floating-point Arithmetic},
988 @article{ dgoldberg:fp,
989 title={{What every computer scientist should know about floating-point arithmetic}},
990 author={Goldberg, D.},
991 journal={ACM Computing Surveys (CSUR)},
996 publisher={ACM Press New York, NY, USA}
999 @article{ thorup:floatint,
1000 title={{Floats, Integers, and Single Source Shortest Paths}},
1001 author={Thorup, M.},
1002 journal={Journal of Algorithms},
1007 publisher={Academic Press}
1010 @article{ shamos:closest,
1011 title={{Closest-point problems}},
1012 author={Shamos, M. I. and Hoey, D.},
1013 journal={Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science},
1018 @article{ fortune:voronoi,
1019 title={{A sweepline algorithm for Voronoi diagrams}},
1020 author={Fortune, S.},
1021 journal={Algorithmica},
1026 publisher={Springer}
1029 @article{ zhou:nodel,
1030 title={{Efficient minimum spanning tree construction without Delaunay triangulation}},
1031 author={Zhou, H. and Shenoy, N. and Nicholls, W.},
1032 journal={Information Processing Letters},
1037 publisher={Elsevier}
1040 @techreport{ eppstein:spanning,
1041 title={{Spanning Trees and Spanners}},
1042 author={Eppstein, D.},
1044 institution={Information and Computer Science, University of California, Irvine}
1047 @article{ garey:steiner,
1048 title={{The Complexity of Computing Steiner Minimal Trees}},
1049 author={Garey, M.R. and Graham, R.L. and Johnson, D.S.},
1050 journal={SIAM Journal on Applied Mathematics},
1057 @article{ garey:rectisteiner,
1058 title={{The Rectilinear Steiner Tree Problem is NP-Complete}},
1059 author={Garey, M.R. and Johnson, D.S.},
1060 journal={SIAM Journal on Applied Mathematics},
1067 @article{ proemel:steiner,
1068 title={{A new approximation algorithm for the Steiner tree problem with performance ratio $5/3$}},
1069 author={Promel, H.J. and Steger, A.},
1070 journal={Journal of Algorithms},
1076 @article{ arora:tspapx,
1077 title={{Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems}},
1079 journal={Journal of the ACM (JACM)},
1084 publisher={ACM Press New York, NY, USA}
1087 @article{ harel:nca,
1088 title={{Fast algorithms for finding nearest common ancestors}},
1089 author={Harel, D. and Tarjan, R.E.},
1090 journal={SIAM Journal on Computing},
1095 publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
1099 author = "R. E. Gomory and T. C. Hu",
1100 title = "Multi-Terminal Network Flows",
1101 journal = "{Journal of SIAM}",
1108 @inproceedings{ bhalgat:ght,
1109 author = {Ramesh Hariharan and Telikepalli Kavitha and Debmalya Panigrahi and Anand Bhalgat},
1110 title = {{An $\widehat\O(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs}},
1111 booktitle = {STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing},
1113 isbn = {978-1-59593-631-8},
1115 location = {San Diego, California, USA},
1116 doi = {http://doi.acm.org/10.1145/1250790.1250879},
1118 address = {New York, NY, USA},
1121 @article{ sleator:trees,
1122 title={{A data structure for dynamic trees}},
1123 author={Sleator, D.D. and Tarjan, R.E.},
1124 journal={Journal of Computer and System Sciences},
1129 publisher={Academic Press, Inc. Orlando, FL, USA}
1133 title={{A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations}},
1134 author={Chernoff, H.},
1135 journal={The Annals of Mathematical Statistics},
1143 @article{ pettie:parallel,
1144 author = {Seth Pettie and Vijaya Ramachandran},
1145 title = {A randomized time-work optimal parallel algorithm for
1146 finding a minimum spanning forest},
1147 journal = {SIAM J. Comput.},
1151 pages = {1879--1895},
1154 @article{ chazelle:softheap,
1155 author = {Bernard Chazelle},
1156 title = {The soft heap: an approximate priority queue with optimal error rate},
1162 pages = {1012--1027},
1163 doi = {http://doi.acm.org/10.1145/355541.355554},
1165 address = {New York, NY, USA},
1168 @article{ propp:randommst,
1169 author = {James Gary Propp and David Bruce Wilson},
1170 title = {How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph},
1171 journal = {J. Algorithms},
1177 doi = {http://dx.doi.org/10.1006/jagm.1997.0917},
1178 publisher = {Academic Press, Inc.},
1179 address = {Duluth, MN, USA},
1182 @article{ vuillemin:binheap,
1183 title={{A Data Structure for Manipulating Priority Queues}},
1184 author={Vuillemin, Jean},
1185 journal={Communications of the ACM},
1192 @article{ hoare:qsort,
1193 title={{Quicksort}},
1194 author={Hoare, Charles Anthony Richard},
1195 journal={The Computer Journal},
1200 publisher={British Computer Society}
1203 @article{ blum:selection,
1204 title={{Time bounds for selection}},
1205 author={Blum, M. and Floyd, R.W. and Pratt, V. and Rivest, R.L. and Tarjan, R.E.},
1206 journal={Journal of Computer and System Sciences},
1213 @article{ hoare:qselect,
1214 author = {Hoare, Charles Anthony Richard},
1215 title = {Algorithm 65: find},
1216 journal = {Communications of the ACM},
1222 doi = {http://doi.acm.org/10.1145/366622.366647},
1224 address = {New York, NY, USA},
1227 @article{ dinitz:treeiso,
1228 title={{On an algorithm of Zemlyachenko for subtree isomorphism}},
1229 author={Dinitz, Y. and Itai, A. and Rodeh, M.},
1230 journal={Information Processing Letters},
1235 publisher={Elsevier}
1238 @inproceedings{ zemlay:treeiso,
1239 title={{Determining tree isomorphism}},
1240 author={Zemlayachenko, V. N.},
1241 booktitle={{Voprosy Kibernetiki, Proceedings of the Seminar on Combinatorial Mathematics}},
1242 location={Moscow 1971},
1243 publisher={{Scientific Council of the Complex Problem ``Kibernetika'', Akad. Nauk SSSR}},
1249 @article{ alstrup:marked,
1250 title={{Marked ancestor problems}},
1251 author={Alstrup, S. and Husfeldt, T. and Rauhe, T.},
1252 journal={Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on},
1257 @article{ arvind:isomorph,
1258 title={{Graph isomorphism is in SPP}},
1259 author={Arvind, V. and Kurur, P. P.},
1260 journal={Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on},
1265 @article{ ackermann:function,
1266 title={{Zum Hilbertschen Aufbau der reellen Zahlen}},
1267 author={Ackermann, W.},
1268 journal={Mathematische Annalen},
1273 publisher={Springer},
1277 @article{ klazar:gdss,
1278 title={{Generalized Davenport--Schinzel Sequences: Results, problems, and applications}},
1279 author={Klazar, M.},
1280 journal={INTEGERS: The Electronic Journal of Combinatorial Number Theory},
1287 @inproceedings{ fredman:cellprobe,
1288 author = {M. Fredman and M. Saks},
1289 title = {The cell probe complexity of dynamic data structures},
1290 booktitle = {STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing},
1292 isbn = {0-89791-307-8},
1294 location = {Seattle, Washington, United States},
1295 doi = {http://doi.acm.org/10.1145/73007.73040},
1297 address = {New York, NY, USA},
1300 @article{ henzinger:randdyn,
1301 title={{Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation}},
1302 author={Henzinger, M.R. and King, V.},
1303 journal={Journal of the ACM},
1310 @article{ holm:polylog,
1311 title={{Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity}},
1312 author={Holm, J. and de Lichtenberg, K. and Thorup, M.},
1313 journal={Journal of the ACM (JACM)},
1318 publisher={ACM Press New York, NY, USA}
1321 @article{ frederickson:dynamic,
1322 title={{Data structures for on-line updating of minimum spanning trees, with applications}},
1323 author={Frederickson, G. N.},
1324 journal={SIAM Journal of Computing},
1330 @article{ eppstein:sparsify,
1331 title={{Sparsification --- a technique for speeding up dynamic graph algorithms}},
1332 author={Eppstein, D. and Galil, Z. and Italiano, G.F. and Nissenzweig, A.},
1333 journal={Journal of the ACM},
1338 publisher={ACM Press New York, NY, USA}
1341 @article{ henzinger:mst,
1342 title={{Maintaining minimum spanning trees in dynamic graphs}},
1343 author={Henzinger, M.R. and King, V.},
1344 journal={Proceedings of the 24th International Colloquium on Automata, Languages and Programming},
1347 publisher={Springer}
1350 @mastersthesis { mares:dga,
1351 title={{Dynamick\'e grafov\'e algoritmy}},
1352 author={Martin Mare\v{s}},
1353 school={Charles University in Prague, Faculty of Math and Physics},
1357 @techreport{ henzinger:twoec,
1358 title = {Fully dynamic 2-edge-connectivity algorithm in polylogarithmic time per operation},
1359 author = {Monika Rauch Henzinger and Valerie King},
1360 type = {Technical note},
1361 institution = {Digital Equipment Corp., Systems Research Ctr.},
1362 address = {130 Lytton Rd., Palo Alto, CA, 94301, USA},
1363 number = {1997-004},
1366 url = {http://gatekeeper.dec.com/pub/DEC/SRC/technical-notes/abstracts/src-tn-1997-004.html}
1370 author = {Mark H. Overmars},
1371 title = {Design of Dynamic Data Structures},
1373 isbn = {038712330X},
1374 publisher = {Springer-Verlag New York, Inc.},
1375 address = {Secaucus, NJ, USA},
1376 series={{Lecture Notes in Computer Science}},