1 @inproceedings{ bender:lca,
2 author = "Bender, M. A. and Farach-Colton, M.",
3 title = "The {LCA} Problem Revisited",
4 booktitle = "Latin American Theoretical {INformatics}",
7 url = "citeseer.ist.psu.edu/bender00lca.html"
10 @article{ frederickson:ambivalent,
11 author = "Frederickson, Greg N.",
12 title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
13 journal={SIAM Journal on Computing},
20 @inproceedings{ frederickson:ambifocs,
21 author = "Greg N. Frederickson",
22 title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
23 booktitle = "{IEEE} Symposium on Foundations of Computer Science",
26 url = "citeseer.ist.psu.edu/frederickson91ambivalent.html"
29 @article{ tarjan:wcsetunion,
30 author = {Robert E. Tarjan and Jan van Leeuwen},
31 title = {Worst-case Analysis of Set Union Algorithms},
32 journal = {Journal of the ACM},
38 doi = {http://doi.acm.org/10.1145/62.2160},
41 @article{ tarjan:setunion,
42 title={{Efficiency of a Good But Not Linear Set Union Algorithm}},
43 author={Tarjan, R. E.},
44 journal={Journal of the ACM},
51 @inproceedings { fw:transdich,
52 author = "M. Fredman and D. E. Willard",
53 title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}",
54 booktitle={FOCS '90: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science},
60 author = {Peter van Emde Boas},
61 title = {Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space},
62 journal = {Information Processing Letters},
67 bibsource = {DBLP, http://dblp.uni-trier.de}
70 @article{ benamram:pm,
71 author = "Ben-Amram, A. M.",
72 title = {{What is a ``Pointer Machine''?}},
73 journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
76 url = "citeseer.ist.psu.edu/ben-amram95what.html" }
78 @article{ matsui:planar,
79 author = "Tomomi Matsui",
80 title = "{The Minimum Spanning tree Problem on a Planar Graph}",
81 journal = "Discrete Applied Mathematics",
85 url = "citeseer.nj.nec.com/2319.html"
88 @article{ chazelle:ackermann,
89 author = "Bernard Chazelle",
90 title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
91 journal = "Journal of the ACM",
98 @inproceedings{ chazelle:almostacker,
99 title={{A faster deterministic algorithm for minimum spanning trees}},
100 author={Chazelle, Bernard},
101 booktitle={FOCS '97: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science},
106 @article{ nesetril:history,
107 author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
108 title = "{Some remarks on the history of MST-problem}",
109 journal = "Archivum Mathematicum",
110 publisher = "Masaryk University",
111 address = "Brno, Czech Republic",
117 @article{ nesetril:boruvka,
118 author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
119 title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
120 journal = "Discrete Mathematics",
121 volume = "233(1--3)",
126 @incollection { nesetril:minors,
127 author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
128 title = "{Colorings and Homomorphisms of Minor Closed Classes}",
129 booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
130 editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
133 publisher = "Springer Verlag"
136 @article { boruvka:ojistem,
137 author = "Otakar Bor{\accent23u}vka",
138 title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
139 journal = "Pr\'ace moravsk\'e p\v{r}\'\i{}rodov\v{e}deck\'e spole\v{c}nosti v~Brn\v{e}",
143 note = "In Czech with German summary"
146 @article { boruvka:networks,
147 author = "Otakar Bor{\accent23u}vka",
148 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)}",
149 journal = "Elektronick\'y obzor",
156 @article { jarnik:ojistem,
157 author = "Vojt\v{e}ch Jarn\'\i{}k",
158 title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
159 journal = "Pr\'ace moravsk\'e p\v{r}\'\i{}rodov\v{e}deck\'e spole\v{c}nosti v~Brn\v{e}",
167 author = "Robert E. Tarjan",
168 title = "{Data structures and network algorithms}",
169 series = "{CMBS-NSF Regional Conference Series in Applied Mathematics}",
172 publisher = "Society for Industrial and Applied Mathematics"
175 @techreport { pettie:ackermann,
176 author = "Seth Pettie",
177 title = "{Finding minimum spanning trees in $\O(m\timesalpha(m,n))$ time}",
178 institution = "Univ. of Texas at Austin",
184 @article{ pettie:optimal,
185 author = {Seth Pettie and Vijaya Ramachandran},
186 title= {An optimal minimum spanning tree algorithm},
187 journal = {Journal of the ACM},
194 @inproceedings { pettie:optimal-conf,
195 author = "Seth Pettie and Vijaya Ramachandran",
196 title = "{An Optimal Minimum Spanning Tree Algorithm}",
197 booktitle = "{Proceedings of ICALP 2000}",
202 @article { pettie:alpha,
203 title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}},
206 publisher={University of Texas at Austin Austin, TX, USA}
209 @article { karger:randomized,
210 author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
211 title = "{A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees}",
212 journal = "Journal of the ACM",
219 @inproceedings { karger:sampling,
220 title={Random sampling in matroids, with applications to graph connectivity and minimum spanning trees},
221 author={Karger, D. R.},
222 booktitle={FOCS '93: Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science},
227 @article{ chan:backward,
228 title={{Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees}},
229 author={Chan, T. M.},
230 journal={Information Processing Letters},
237 @article { frederickson:online,
238 author = "Greg N. Frederickson",
239 title = "{Data structures for on-line updating of minimum spanning trees}",
240 journal = "{SIAM Journal on Computing}",
247 author = "Martin Mare\v{s}",
248 title = "{Two linear time algorithms for MST on minor closed graph classes}",
249 journal = "{Archivum Mathematicum}",
250 publisher = "Masaryk University",
251 address = "Brno, Czech Republic",
257 @inproceedings{ mm:rank,
258 author = "Martin Mare\v{s} and Milan Straka",
259 title = "Linear-Time Ranking of Permutations",
260 booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium",
261 location = "Eilat, Israel, October 8--10, 2007",
263 series = {{Lecture Notes in Computer Science}},
265 publisher = "Springer Verlag",
269 @article{ ft:fibonacci,
270 author = {Michael L. Fredman and Robert Endre Tarjan},
271 title = {Fibonacci heaps and their uses in improved network optimization algorithms},
272 journal = {Journal of the ACM},
278 doi = {http://doi.acm.org/10.1145/28869.28874},
281 @article{ komlos:verify,
282 author = {J{\'a}nos Koml{\'o}s},
283 title = {Linear verification for spanning trees.},
284 journal = {Combinatorica},
289 bibsource = {DBLP, http://dblp.uni-trier.de}
292 @inproceedings{ king:verify,
293 author = "Valerie King",
294 title = "A Simpler Minimum Spanning Tree Verification Algorithm",
295 booktitle = "{Algorithms and Data Structures --- WADS '95: 4th International Workshop}",
298 location = "Kingston, Canada",
300 series = "Lecture Notes in Computer Science",
301 publisher = "Springer Verlag",
302 url = "citeseer.ist.psu.edu/king95simpler.html"
305 @article{ king:verifytwo,
306 title={{A Simpler Minimum Spanning Tree Verification Algorithm}},
307 author={King, Valerie},
308 journal={Algorithmica},
315 author = "Alexander Schrijver",
316 title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
317 series = "Algorithms and Combinatorics",
320 publisher = "Springer Verlag"
323 @inproceedings{ thorup:aczero,
324 author = {Mikkel Thorup},
325 title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
326 booktitle = {SODA 2003: Proceedings of the 14th annual ACM-SIAM Symposium on Discrete algorithms},
328 isbn = {0-89871-538-5},
330 location = {Baltimore, Maryland},
333 @article{ kruskal:mst,
334 title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
335 author={Kruskal, Jr, J. B.},
336 journal={Proceedings of the American Mathematical Society},
345 title={{Graph Theory}},
346 author={Diestel, R.},
348 publisher={Springer Verlag}
351 @article{ graham:msthistory,
352 title={{On the history of the minimum spanning tree problem}},
353 author={Graham, R. L. and Hell, P.},
354 journal={Annals of the History of Computing},
361 @article{ cayley:trees,
362 title={{A theorem on trees}},
363 author={Cayley, Arthur},
364 journal={Quarterly Journal of Mathematics},
370 @article{ dijkstra:mst,
371 title={{A note on two problems in connexion with graphs}},
372 author = "Dijkstra, E. W.",
373 journal={Numerische Mathematik},
378 publisher={Springer Verlag}
382 author = "Prim, R. C.",
383 title = "Shortest connection networks and some generalizations",
384 journal = "Bell System Technical Journal",
390 @article{ choquet:mst,
391 title={{Etude de certains r{\'e}seaux de routes}},
392 author={Choquet, Gustave},
393 journal={Comptes-rendus de l'Académie des Sciences},
400 @incollection { sollin:mst,
401 title={{Le trace de canalisation}},
403 booktitle={Programming, Games, and Transportation Networks},
404 editor={Berge, C. and Ghouilla-Houri, A.},
405 publisher={Wiley, New York},
410 @article{ boyer:cutting,
411 title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
412 author={Boyer, J. M. and Myrvold, W. J.},
413 journal={Journal of Graph Algorithms and Applications},
420 @inproceedings{ takaoka:twothree,
421 title={{Theory of 2-3 Heaps}},
422 author={Takaoka, T. and Christchurch, N. Z.},
423 booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON '99},
424 location={Tokyo, Japan},
427 publisher={Springer Verlag},
428 series={{Lecture Notes in Computer Science}},
432 @inproceedings{ takaoka:trinomial,
433 title={{Theory of Trinomial Heaps}},
434 author={Takaoka, Tadao},
435 booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
436 location={Sydney, Australia},
439 publisher={Springer Verlag},
440 series={{Lecture Notes in Computer Science}},
445 title={{Introduction to Algorithms}},
446 author={Leiserson, C. E. and Rivest, R. L. and Cormen, T. H. and Stein, C.},
448 publisher={McGraw-Hill}
451 @article{ pettie:onlineverify,
452 author = {Seth Pettie},
453 title = {An Inverse-{A}ckermann Type Lower Bound for Online
454 Minimum Spanning Tree Verification},
455 journal = {Combinatorica},
462 @inproceedings{ pettie:onlineverify-conf,
463 author = "S. Pettie",
464 title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
465 tree verification problem",
466 booktitle = "FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science",
468 url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
471 @article{ dixon:verify,
472 author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
473 title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
474 journal = "SIAM Journal of Computing",
479 url = "citeseer.ist.psu.edu/dixon92verification.html"
482 @inproceedings{ pettie:minirand,
483 author = {Seth Pettie and Vijaya Ramachandran},
484 title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
485 booktitle = {SODA 2002: Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms},
487 isbn = {0-89871-513-X},
489 location = {San Francisco, California},
492 @inproceedings{ buchsbaum:verify,
493 title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
494 author={Buchsbaum, A. L. and Kaplan, H. and Rogers, A. and Westbrook, J. R.},
495 booktitle={STOC 1998: Proceedings of the 30th annual ACM Symposium on Theory of Computing},
500 @article{ bacala:parametric,
501 title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
502 author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
503 journal={Theoretical Computer Science},
511 @inproceedings{ katriel:cycle,
512 author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
513 title = "A practical minimum spanning tree algorithm using the cycle property",
514 booktitle = "Algorithms --- ESA 2003: 11th European Symposium",
516 series = "Lecture Notes in Computer Science",
518 publisher = "Springer Verlag",
520 url = "citeseer.ist.psu.edu/katriel03practical.html"
523 @article{ alstrup:nca,
524 title={{Nearest Common Ancestors: A Survey and a new Distributed Algorithm}},
525 author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
526 journal={Proceedings of the 14th annual ACM Symposium on Parallel algorithms and architectures},
532 title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
533 author={Gabow, H. N. and Galil, Z. and Spencer, T. and Tarjan, R. E.},
534 journal={Combinatorica},
539 publisher={Springer Verlag}
542 @online{ eisner:tutorial,
543 author = {Jason Eisner},
544 title = {{State-of-the-Art Algorithms for Minimum Spanning
545 Trees: A~Tutorial Discussion}},
546 note = {Manuscript available online (78 pages), University of Pennsylvania},
548 url = {http://cs.jhu.edu/{\char126}jason/papers/\#ms97},
552 title={{On finding lowest common ancestors in trees.}},
553 author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
554 journal={SIAM Journal on Computing},
560 @book{ knuth:fundalg,
561 author = {Donald E. Knuth},
562 title = {The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms},
564 isbn = {0-201-89683-4},
565 publisher = {Addison Wesley Longman Publishing Co., Inc.},
568 @book{ knuth:seminalg,
569 author = {Donald E. Knuth},
570 title = {The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical algorithms},
572 isbn = {978-0-201-89684-8},
573 publisher = {Addison Wesley Longman Publishing Co., Inc.},
577 author = {Donald E. Knuth},
578 title = {{The Art of Computer Programming, Volume 3 (2nd ed.): Sorting and Searching}},
580 isbn = {978-0-201-89685-5},
581 publisher = {Addison Wesley Longman Publishing Co., Inc.},
584 @inproceedings{ hagerup:wordram,
585 author = {Torben Hagerup},
586 title = {{Sorting and Searching on the Word RAM}},
587 booktitle = {STACS '98: Proceedings of the 15th annual Symposium on Theoretical Aspects of Computer Science},
589 isbn = {3-540-64230-7},
593 @inproceedings{ cook:ram,
594 author = {Stephen A. Cook and Robert A. Reckhow},
595 title = {Time-bounded random access machines},
596 booktitle = {STOC '72: Proceedings of the fourth annual ACM Symposium on Theory of Computing},
599 location = {Denver, Colorado, United States},
600 doi = {http://doi.acm.org/10.1145/800152.804898},
603 @book{ okasaki:funcds,
604 author = {Chris Okasaki},
605 title = {Purely Functional Data Structures},
607 publisher = {Cambridge University Press}
610 @book { intel:pentium,
611 author = {{Intel Corp.}},
612 title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference},
614 publisher = {Intel Corp.},
615 xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
618 @article{ hagerup:dd,
619 title={{Deterministic Dictionaries}},
620 author={Hagerup, T. and Miltersen, P. B. and Pagh, R.},
621 journal={Journal of Algorithms},
628 @article{ fredman:sst,
629 title={{Storing a Sparse Table with $\O(1)$ Worst Case Access Time}},
630 author={Fredman, M. L. and Koml{\'o}s, J. and Szemer{\'e}di, E.},
631 journal={Journal of the ACM},
638 @book{ motwani:randalg,
639 title={{Randomized Algorithms}},
640 author={Motwani, R. and Raghavan, P.},
642 publisher={Cambridge University Press}
646 title={{Surpassing the information theoretic bound with fusion trees}},
647 author={Fredman, M. L. and Willard, D. E.},
648 journal={Journal of Computer and System Sciences},
655 @inproceedings{ han:detsort,
656 title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}},
658 booktitle={STOC 2002: Proceedings of the 34th annual ACM Symposium on Theory of Computing},
663 @inproceedings{ hanthor:randsort,
664 title={{Integer Sorting in $\O(n\sqrt{\log\log n})$ Expected Time and Linear Space}},
665 author={Han, Y. and Thorup, M.},
666 booktitle={FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science},
671 @inproceedings{ ito:newrap,
672 title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}},
673 author={Ito, M. and Takagi, N. and Yajima, S.},
674 booktitle={Proceedings of the 12th IEEE Symposium on Computer Arithmetic},
679 @inproceedings{ brodnik:lsb,
680 title={{Computation of the least significant set bit}},
681 author={Brodnik, A.},
682 booktitle={Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia},
686 @article{ turan:succinct,
687 title={{Succinct representation of graphs.}},
688 author={Tur\'an, G.},
689 journal={Discrete Applied Mathematics},
696 @book{ jones:haskell,
697 title={{Haskell 98 Language and Libraries: The Revised Report}},
698 author={Jones, P. and Simon, L.},
700 publisher={Cambridge University Press}
703 @article{ mader:dens,
704 title={{Homomorphieeigenschaften und mittlere Kantendichte von Graphen}},
706 journal={Mathematische Annalen},
711 publisher={Springer Verlag},
715 @inproceedings{ gustedt:parallel,
716 author = "Jens Gustedt",
717 title = "Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel",
718 booktitle = "STACS '98: Proceedings of the 15th annual Symposium on Theoretical Aspects of Computer Science",
721 url = "citeseer.ist.psu.edu/223918.html"
724 @article{ myrvold:rank,
725 title={{Ranking and unranking permutations in linear time}},
726 author={Myrvold, W. J. and Ruskey, F.},
727 journal={Information Processing Letters},
734 @inproceedings{ critani:rau,
735 title={{Ranking and unranking permutations with applications}},
736 author={Critani, F. and Dall'Aglio, M. and Di Biase, G.},
737 booktitle={Innovation in Mathematics: Proceedings of Second International Mathematica Symposium},
742 @article{ ruskey:ham,
743 title={{The Hamiltonicity of directed-Cayley graphs (or: A tale of backtracking)}},
744 author={Ruskey, F. and Jiang, M. and Weston, A.},
745 journal={Discrete Applied Mathematics},
751 @article{ ruskey:hce,
752 title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n$}},
753 author={Ruskey, F. and Savage, C. D.},
754 journal={SIAM Journal on Discrete Mathematics},
761 @article{ liehe:raulow,
762 title={{Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis}},
763 author={Liebehenschel, J.},
764 journal={Journal of Automata, Languages and Combinatorics},
771 @book{ reingold:catp,
772 title={{Combinatorial Algorithms: Theory and Practice}},
773 author={Reingold, E. M.},
775 publisher={Prentice Hall College Div}
778 @inproceedings{ dietz:oal,
779 author = {Paul F. Dietz},
780 title = {Optimal Algorithms for List Indexing and Subset Rank},
781 booktitle = {WADS '89: Proceedings of the Workshop on Algorithms and Data Structures},
783 isbn = {3-540-51542-9},
788 title={{The 15 Puzzle Book}},
789 author={Slocum, J. and Sonneveld D.},
791 publisher={The Slocum Puzzle Foundation, Beverly Hills, CA, USA}
795 title={{Graph minors: XX. Wagner's Conjecture}},
796 author={Robertson, N. and Seymour, P. D.},
797 journal={Journal of Combinatorial Theory Series B},
805 title={{Invitation to Discrete Mathematics}},
806 author={Matou{\v{s}}ek, J. and Ne{\v{s}}et{\v{r}}il, J.},
808 publisher={Oxford University Press}
811 @book{ stanley:econe,
812 title={{Enumerative Combinatorics. Vol. 1 (2nd ed.)}},
813 author={Stanley, R. P.},
814 publisher={Cambridge University Press},
818 @article{ kaplansky:rooks,
819 title={{The problem of the rooks and its applications}},
820 author={Kaplansky, I. and Riordan, J.},
821 journal={Duke Mathematical Journal},
826 publisher={Duke University Press}
829 @article{ dinic:flow,
830 author = {E. A. Dinic},
831 title = {Algorithm for solution of a problem of maximum flow in networks with power estimation},
832 journal = {Soviet Math. Dokl.},
838 @article{ even:dinic,
839 author = {Shimon Even and Robert Endre Tarjan},
840 title = {Network Flow and Testing Graph Connectivity},
843 journal = {SIAM Journal on Computing},
847 url = {http://link.aip.org/link/?SMJ/4/507/1},
848 doi = {10.1137/0204043}
851 @article{ valiant:permanent,
852 title={{The complexity of computing the permanent}},
853 author={Valiant, L. G.},
854 journal={Theoretical Computer Science},
861 @article{ jerrum:permanent,
862 title={{A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries}},
863 author={Jerrum, M. and Sinclair, A. and Vigoda, E.},
864 journal={Journal of the ACM},
871 /* HACK: bibtex cannot handle a part of a book with its own name */
872 @inproceedings{ kasteleyn:crystals,
873 title={{Graph theory and crystal physics}},
874 author={Kasteleyn, P. W.},
875 booktitle={Graph Theory and Theoretical Physics},
876 publisher={Academic Press, London},
881 @inproceedings{ yuster:matching,
882 title={{Maximum matching in graphs with an excluded minor}},
883 author={Yuster, R. and Zwick, U.},
884 booktitle={SODA 2007: Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms},
889 @article{ mucha:matching,
890 title={{Maximum Matchings in Planar Graphs via Gaussian Elimination}},
891 author={Mucha, M. and Sankowski, P.},
892 journal={Algorithmica},
899 @article {lovasz:minors,
900 title={{Graph Minor Theory}},
901 author={Lov\'asz, L.},
902 journal={Bulletin of the American Mathematical Society},
909 @article{ andersson:fusion,
910 title={{Fusion trees can be implemented with AC$^0$ instructions only}},
911 author={Andersson, A. and Miltersen, P. B. and Thorup, M.},
912 journal={Theoretical Computer Science},
920 @article{ thorup:rampq,
921 title={{On RAM priority queues}},
923 journal={SIAM Journal on Computing},
930 @article{ thorup:pqsssp,
931 title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
933 journal={STOC 2003: Proceedings of the 35th ACM Symposium on Theory of Computing},
938 @article{ chazelle:mstapprox,
939 title={{Approximating the Minimum Spanning Tree Weight in Sublinear Time}},
940 author={Chazelle, B. and Rubinfeld, R. and Trevisan, L.},
941 journal={SIAM Journal on Computing},
947 @inproceedings{ czumaj:metric,
948 author = {Artur Czumaj and Christian Sohler},
949 title = {Estimating the weight of metric minimum spanning trees in sublinear-time},
950 booktitle = {STOC 2004: Proceedings of the 36th annual ACM Symposium on Theory of Computing},
952 isbn = {1-58113-852-0},
954 location = {Chicago, IL, USA},
957 @inproceedings{ czumaj:euclidean,
958 author = {Artur Czumaj and Funda Erg\"{u}n and Lance Fortnow and Avner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler},
959 title = {{Sublinear-time approximation of Euclidean minimum spanning tree}},
960 booktitle = {SODA 2003: Proceedings of the 14th annual ACM-SIAM Symposium on Discrete Algorithms},
962 isbn = {0-89871-538-5},
964 publisher = {Society for Industrial and Applied Mathematics},
969 title = {IEEE Standard 754-1985 for Binary Floating-point Arithmetic},
974 @article{ dgoldberg:fp,
975 title={{What every computer scientist should know about floating-point arithmetic}},
976 author={Goldberg, D.},
977 journal={ACM Computing Surveys},
984 @article{ thorup:floatint,
985 title={{Floats, Integers, and Single Source Shortest Paths}},
987 journal={Journal of Algorithms},
994 @article{ shamos:closest,
995 title={{Closest-point problems}},
996 author={Shamos, M. I. and Hoey, D.},
997 journal={FOCS '75: Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science},
1002 @article{ fortune:voronoi,
1003 title={{A sweepline algorithm for Voronoi diagrams}},
1004 author={Fortune, S.},
1005 journal={Algorithmica},
1012 @article{ zhou:nodel,
1013 title={{Efficient minimum spanning tree construction without Delaunay triangulation}},
1014 author={Zhou, H. and Shenoy, N. and Nicholls, W.},
1015 journal={Information Processing Letters},
1022 @techreport{ eppstein:spanning,
1023 title={{Spanning Trees and Spanners}},
1024 author={Eppstein, D.},
1026 institution={Information and Computer Science, University of California, Irvine},
1030 @article{ garey:steiner,
1031 title={{The Complexity of Computing Steiner Minimal Trees}},
1032 author={Garey, M. R. and Graham, R. L. and Johnson, D. S.},
1033 journal={SIAM Journal on Applied Mathematics},
1040 @article{ garey:rectisteiner,
1041 title={{The Rectilinear Steiner Tree Problem is NP-Complete}},
1042 author={Garey, M. R. and Johnson, D. S.},
1043 journal={SIAM Journal on Applied Mathematics},
1050 @article{ proemel:steiner,
1051 title={{A new approximation algorithm for the Steiner tree problem with performance ratio $5/3$}},
1052 author={Promel, H. J. and Steger, A.},
1053 journal={Journal of Algorithms},
1059 @article{ arora:tspapx,
1060 title={{Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems}},
1062 journal={Journal of the ACM},
1069 @article{ harel:nca,
1070 title={{Fast algorithms for finding nearest common ancestors}},
1071 author={Harel, D. and Tarjan, R. E.},
1072 journal={SIAM Journal on Computing},
1080 author = "R. E. Gomory and T. C. Hu",
1081 title = "Multi-Terminal Network Flows",
1082 journal = "{Journal of SIAM}",
1089 @inproceedings{ bhalgat:ght,
1090 author = {Ramesh Hariharan and Telikepalli Kavitha and Debmalya Panigrahi and Anand Bhalgat},
1091 title = {{An $\widetilde\O(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs}},
1092 booktitle = {STOC 2007: Proceedings of the 39th annual ACM Symposium on Theory of Computing},
1094 isbn = {978-1-59593-631-8},
1096 location = {San Diego, California, USA},
1097 doi = {http://doi.acm.org/10.1145/1250790.1250879},
1100 @article{ sleator:trees,
1101 title={{A data structure for dynamic trees}},
1102 author={Sleator, D. D. and Tarjan, R. E.},
1103 journal={Journal of Computer and System Sciences},
1111 title={{A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations}},
1112 author={Chernoff, H.},
1113 journal={The Annals of Mathematical Statistics},
1121 @article{ pettie:parallel,
1122 author = {Seth Pettie and Vijaya Ramachandran},
1123 title = {A randomized time-work optimal parallel algorithm for
1124 finding a minimum spanning forest},
1125 journal = {SIAM Journal of Computing},
1129 pages = {1879--1895},
1132 @article{ chazelle:softheap,
1133 author = {Bernard Chazelle},
1134 title = {The soft heap: an approximate priority queue with optimal error rate},
1135 journal = {Journal of the ACM},
1140 pages = {1012--1027},
1141 doi = {http://doi.acm.org/10.1145/355541.355554},
1144 @article{ propp:randommst,
1145 author = {James Gary Propp and David Bruce Wilson},
1146 title = {How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph},
1147 journal = {Journal of Algorithms},
1153 doi = {http://dx.doi.org/10.1006/jagm.1997.0917},
1156 @article{ vuillemin:binheap,
1157 title={{A Data Structure for Manipulating Priority Queues}},
1158 author={Vuillemin, Jean},
1159 journal={Communications of the ACM},
1166 @article{ hoare:qsort,
1167 title={{Quicksort}},
1168 author={Hoare, Charles Anthony Richard},
1169 journal={The Computer Journal},
1174 publisher={British Computer Society}
1177 @article{ blum:selection,
1178 title={{Time bounds for selection}},
1179 author={Blum, M. and Floyd, R. W. and Pratt, V. and Rivest, R. L. and Tarjan, R. E.},
1180 journal={Journal of Computer and System Sciences},
1187 @article{ hoare:qselect,
1188 author = {Hoare, Charles Anthony Richard},
1189 title = {Algorithm 65: find},
1190 journal = {Communications of the ACM},
1196 doi = {http://doi.acm.org/10.1145/366622.366647},
1199 @article{ dinitz:treeiso,
1200 title={{On an algorithm of Zemlyachenko for subtree isomorphism}},
1201 author={Dinitz, Y. and Itai, A. and Rodeh, M.},
1202 journal={Information Processing Letters},
1209 @inproceedings{ zemlay:treeiso,
1210 title={{Determining tree isomorphism}},
1211 author={Zemlayachenko, V. N.},
1212 booktitle={{Voprosy Kibernetiki, Proceedings of the Seminar on Combinatorial Mathematics}},
1213 location={Moscow 1971},
1214 publisher={{Scientific Council of the Complex Problem ``Kibernetika'', Akad. Nauk SSSR}},
1220 @inproceedings{ alstrup:marked,
1221 title={{Marked ancestor problems}},
1222 author={Alstrup, S. and Husfeldt, T. and Rauhe, T.},
1223 booktitle={FOCS '98: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science},
1228 @inproceedings{ arvind:isomorph,
1229 title={{Graph isomorphism is in SPP}},
1230 author={Arvind, V. and Kurur, P. P.},
1231 booktitle={FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science},
1236 @article{ ackermann:function,
1237 title={{Zum Hilbertschen Aufbau der reellen Zahlen}},
1238 author={Ackermann, W.},
1239 journal={Mathematische Annalen},
1244 publisher={Springer},
1248 @article{ klazar:gdss,
1249 title={{Generalized Davenport--Schinzel Sequences: Results, problems, and applications}},
1250 author={Klazar, M.},
1251 journal={INTEGERS: The Electronic Journal of Combinatorial Number Theory},
1257 @inproceedings{ fredman:cellprobe,
1258 author = {M. Fredman and M. Saks},
1259 title = {The cell probe complexity of dynamic data structures},
1260 booktitle = {STOC '89: Proceedings of the 21st annual ACM Symposium on Theory of Computing},
1262 isbn = {0-89791-307-8},
1264 location = {Seattle, Washington, United States},
1265 doi = {http://doi.acm.org/10.1145/73007.73040},
1268 @article{ henzinger:randdyn,
1269 title={{Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation}},
1270 author={Henzinger, M. R. and King, V.},
1271 journal={Journal of the ACM},
1278 @article{ holm:polylog,
1279 title={{Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity}},
1280 author={Holm, J. and de Lichtenberg, K. and Thorup, M.},
1281 journal={Journal of the ACM},
1288 @article{ frederickson:dynamic,
1289 title={{Data structures for on-line updating of minimum spanning trees, with applications}},
1290 author={Frederickson, G. N.},
1291 journal={SIAM Journal of Computing},
1297 @article{ eppstein:sparsify,
1298 title={{Sparsification --- a technique for speeding up dynamic graph algorithms}},
1299 author={Eppstein, D. and Galil, Z. and Italiano, G. F. and Nissenzweig, A.},
1300 journal={Journal of the ACM},
1307 @inproceedings{ henzinger:mst,
1308 title={{Maintaining minimum spanning trees in dynamic graphs}},
1309 author={Henzinger, M. R. and King, V.},
1310 booktitle={ICALP '97: Proceedings of the 24th International Colloquium on Automata, Languages and Programming},
1315 @mastersthesis { mares:dga,
1316 title={{Dynamick\'e grafov\'e algoritmy (Dynamic Graph Algorithms)}},
1317 author={Martin Mare\v{s}},
1318 school={Charles University in Prague, Faculty of Math and Physics},
1323 @techreport{ henzinger:twoec,
1324 title = {Fully dynamic 2-edge-connectivity algorithm in polylogarithmic time per operation},
1325 author = {Monika Rauch Henzinger and Valerie King},
1326 type = {Technical note},
1327 institution = {Digital Equipment Corp., Systems Research Center},
1328 number = {1997-004},
1330 url = {http://gatekeeper.dec.com/pub/DEC/SRC/technical-notes/abstracts/src-tn-1997-004.html}
1334 author = {Mark H. Overmars},
1335 title = {Design of Dynamic Data Structures},
1337 isbn = {038712330X},
1338 publisher = {Springer Verlag},
1339 series={{Lecture Notes in Computer Science}},
1343 @article{ eppstein:ksmallest,
1344 title={{Finding the $k$~Smallest Spanning Trees}},
1345 author={Eppstein, D.},
1351 publisher={Springer Verlag}
1354 @article{ katoh:ksmallest,
1355 title={{An Algorithm for Finding\$ K\$ Minimum Spanning Trees}},
1356 author={Katoh, N. and Ibaraki, T. and Mine, H.},
1357 journal={SIAM Journal on Computing},
1363 @inproceedings{ thorup:nearopt,
1364 author = {Mikkel Thorup},
1365 title = {Near-optimal fully-dynamic graph connectivity},
1366 booktitle = {STOC 2000: Proceedings of the 32nd annual ACM Symposium on Theory of Computing},
1368 isbn = {1-58113-184-4},
1370 location = {Portland, Oregon, United States},
1371 doi = {http://doi.acm.org/10.1145/335305.335345},
1374 @article{ henzinger:lowerbounds,
1375 title={{Lower Bounds for Fully Dynamic Connectivity Problems in Graphs}},
1376 author={Henzinger, M. R. and Fredman, M. L.},
1377 journal={Algorithmica},
1384 @article{ thorup:usssp,
1385 title={{Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time}},
1386 author={Thorup, Mikkel},
1387 journal={Journal of the ACM},
1394 @article{ thorup:sssp,
1395 author = {Mikkel Thorup},
1396 title = {Integer priority queues with decrease key in constant time and the single source shortest paths problem},
1397 journal = {Journal of Computer and System Sciences},
1403 doi = {http://dx.doi.org/10.1016/j.jcss.2004.04.003},
1406 @inproceedings{ hagerup:sssp,
1407 author = {Torben Hagerup},
1408 title = {{Improved Shortest Paths on the Word RAM}},
1409 booktitle = {ICALP 2000: Proceedings of the 27th International Colloquium on Automata, Languages and Programming},
1411 isbn = {3-540-67715-1},
1415 @techreport { hakmem,
1416 author = "Beeler, Michael and Gosper, R. William and Schroeppel, Rich",
1418 institution = "Massachusetts Institute of Technology",
1424 @book{ oxley:matroids,
1425 title={{Matroid Theory}},
1426 author={Oxley, J. G.},
1428 publisher={Oxford University Press}
1431 @article{ katoh:kmin,
1432 author = {N. Katoh and T. Ibaraki and H. Mine},
1433 title = {An Algorithm for Finding $K$ Minimum Spanning Trees},
1435 journal = {SIAM Journal on Computing},
1441 @article{ chong:parallel,
1442 author = {Ka Wong Chong and Yijie Han and Tak Wah Lam},
1443 title = {Concurrent threads and optimal parallel minimum spanning trees algorithm},
1444 journal = {Journal of the ACM},
1450 doi = {http://doi.acm.org/10.1145/375827.375847},
1453 @article{ moret:expmst,
1454 title={{An Empirical Assessment of Algorithms for Constructing a Minimum Spanning Tree}},
1455 author={Moret, B. M. E. and Shapiro, H. D.},
1456 journal={Computational Support for Discrete Mathematics: DIMACS Workshop, March 12-14, 1992},
1458 publisher={American Mathematical Society}
1461 @article{ fredman:pairingheap,
1462 title={{The pairing heap: A new form of self-adjusting heap}},
1463 author={Fredman, M. L. and Sedgewick, R. and Sleator, D. D. and Tarjan, R. E.},
1464 journal={Algorithmica},
1471 @inproceedings{ pettie:pairing,
1472 author = {Seth Pettie},
1473 title = {Towards a Final Analysis of Pairing Heaps},
1474 booktitle = {FOCS 2005: Proceedings of the 46rd Annual IEEE Symposium on Foundations of Computer Science},
1479 @book{ jaja:parallel,
1480 title={{An introduction to parallel algorithms}},
1481 author={J{\'a}J{\'a}, J.},
1483 publisher={Addison Wesley Longman Publishing Co., Inc.}
1486 @techreport { mm:ga,
1487 author = "Martin Mare\v{s}",
1488 title = "{Krajinou grafov\'ych algoritm\accent23u (Through the Landscape of Graph Algorithms)}",
1489 institution = "Institut Teoretick\'e Informatiky",
1490 address = "Praha, Czech Republic",
1492 number = "2007--330",
1493 type = "ITI series",
1497 @book { horak:mofivefour,
1498 author = {Hor\'ak, Karel and Mare\v{s}, Martin and Novotn\'y, Peter and \v{S}im\v{s}a, Jarom\'\i{}r and \v{S}vr\v{c}ek, Jaroslav and T\"opfer, Pavel and Zhouf, Jaroslav},
1499 title = {54.~ro\v{c}n\'\i{}k matematick\'e olympi\'ady na st\v{r}edn\'\i{}ch \v{s}kol\'ach (The 54th Year of the Math Olympiad at High Schools)},
1500 publisher = {Jednota \v{c}esk\'ych matematik\accent23u a fyzik\accent23u},
1504 isbn = {80-7015-109-9},
1507 @article{ tarjan:applpc,
1508 author = {Robert Endre Tarjan},
1509 title = {Applications of Path Compression on Balanced Trees},
1510 journal = {Journal of the ACM},
1516 doi = {http://doi.acm.org/10.1145/322154.322161},
1519 @article{ kostochka:lbh,
1520 title={{Lower bound of the Hadwiger number of graphs by their average degree}},
1521 author={Kostochka, A. V.},
1522 journal={Combinatorica},
1529 @article{ thomason:efc,
1530 title={{An extremal function for contractions of graphs}},
1531 author={Thomason, A.},
1532 journal={Mathematical proceedings of the Cambridge Philosophical Society},
1537 publisher={Cambridge University Press}