biblio.bib

   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}",
   5     pages = "88--94",
   6     year = "2000",
   7     url = "citeseer.ist.psu.edu/bender00lca.html"
   8 }
   9
  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},
  14   volume={26},
  15   number={2},
  16   pages={484--538},
  17   year={1997},
  18 }
  19
  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",
  24     pages = "632--641",
  25     year = "1991",
  26     url = "citeseer.ist.psu.edu/frederickson91ambivalent.html"
  27 }
  28
  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},
  33  volume = {31},
  34  number = {2},
  35  year = {1984},
  36  issn = {0004-5411},
  37  pages = {245--281},
  38  doi = {http://doi.acm.org/10.1145/62.2160},
  39 }
  40
  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},
  45   volume={22},
  46   number={2},
  47   pages={215--225},
  48   year={1975},
  49   publisher={ACM Press New York, NY, USA}
  50 }
  51
  52 @inproceedings { fw:transdich,
  53    author = "M. Fredman and D. E. Willard",
  54    title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}",
  55    booktitle={FOCS '90: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science},
  56    pages = "719--725",
  57    year = "1990"
  58 }
  59
  60 @article{ boas:vebt,
  61   author    = {Peter van Emde Boas},
  62   title     = {Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space},
  63   journal   = {Information Processing Letters},
  64   volume    = {6},
  65   number    = {3},
  66   year      = {1977},
  67   pages     = {80-82},
  68   bibsource = {DBLP, http://dblp.uni-trier.de}
  69 }
  70
  71 @article{ benamram:pm,
  72     author = "Ben-Amram, A. M.",
  73     title = {{What is a ``Pointer Machine''?}},
  74     journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
  75     volume = "26",
  76     year = "1995",
  77     url = "citeseer.ist.psu.edu/ben-amram95what.html" }
  78
  79 @article{ matsui:planar,
  80     author = "Tomomi Matsui",
  81     title = "{The Minimum Spanning tree Problem on a Planar Graph}",
  82     journal = "Discrete Applied Mathematics",
  83     volume = "58",
  84     year = "1995",
  85     pages = "91--94",
  86     url = "citeseer.nj.nec.com/2319.html"
  87 }
  88
  89 @article{ chazelle:ackermann,
  90     author = "Bernard Chazelle",
  91     title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
  92     journal = "Journal of the ACM",
  93     volume = "47",
  94     number = {6},
  95     pages = "1028--1047",
  96     year = "2000"
  97 }
  98
  99 @inproceedings{ chazelle:almostacker,
 100   title={{A faster deterministic algorithm for minimum spanning trees}},
 101   author={Chazelle, Bernard},
 102   booktitle={FOCS '97: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science},
 103   pages={22},
 104   year={1997},
 105 }
 106
 107 @article{ nesetril:history,
 108     author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
 109     title = "{Some remarks on the history of MST-problem}",
 110     journal = "Archivum Mathematicum",
 111     volume = "33",
 112     pages = "15--22",
 113     year = "1997"
 114 }
 115
 116 @article{ nesetril:boruvka,
 117     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
 118     title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
 119     journal = "Discrete Mathematics",
 120     volume = "233(1--3)",
 121     pages = "3--36",
 122     year = "2001"
 123 }
 124
 125 @incollection { nesetril:minors,
 126     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
 127     title = "{Colorings and Homomorphisms of Minor Closed Classes}",
 128     booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
 129     editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
 130     year = "2003",
 131     pages = "651--664",
 132     publisher = "Springer Verlag"
 133 }
 134
 135 @article { boruvka:ojistem,
 136     author = "Otakar Bor{\accent23u}vka",
 137     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
 138     journal = "Pr\'ace moravsk\'e p\v{r}\'\i{}rodov\v{e}deck\'e spole\v{c}nosti v~Brn\v{e}",
 139     volume = "III",
 140     year = "1926",
 141     pages = "37--58",
 142     note = "In Czech with German summary"
 143 }
 144
 145 @article { boruvka:networks,
 146     author = "Otakar Bor{\accent23u}vka",
 147     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)}",
 148     journal = "Elektronick\'y obzor",
 149     volume = "15",
 150     year = "1926",
 151     pages = "153--154",
 152     note = "In Czech"
 153 }
 154
 155 @article { jarnik:ojistem,
 156     author = "Vojt\v{e}ch Jarn\'\i{}k",
 157     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
 158     journal = "Pr\'ace moravsk\'e p\v{r}\'\i{}rodov\v{e}deck\'e spole\v{c}nosti v~Brn\v{e}",
 159     volume = "VI",
 160     year = "1930",
 161     pages = "57--63",
 162     note = "In Czech"
 163 }
 164
 165 @book { tarjan:dsna,
 166     author = "Robert E. Tarjan",
 167     title = "{Data structures and network algorithms}",
 168     series = "{CMBS-NSF Regional Conference Series in Applied Mathematics}",
 169     volume = 44,
 170     year = "1983",
 171     publisher = "SIAM"
 172 }
 173
 174 @techreport { pettie:ackermann,
 175     author = "Seth Pettie",
 176     title = "{Finding minimum spanning trees in $\O(m\alpha(m,n))$ time}",
 177     institution = "Univ. of Texas at Austin",
 178     year = "1999",
 179     number = "TR99-23",
 180     type = "Tech Report"
 181 }
 182
 183 @article{ pettie:optimal,
 184  author = {Seth Pettie and Vijaya Ramachandran},
 185  title= {An optimal minimum spanning tree algorithm},
 186  journal = {Journal of the ACM},
 187  volume = {49},
 188  number = {1},
 189  year = {2002},
 190  pages = {16--34},
 191 }
 192
 193 @inproceedings { pettie:optimal-conf,
 194    author = "Seth Pettie and Vijaya Ramachandran",
 195    title = "{An Optimal Minimum Spanning Tree Algorithm}",
 196    booktitle = "{Proceedings of ICALP 2000}",
 197    year = "2000",
 198    pages = "49--60"
 199 }
 200
 201 @article { pettie:alpha,
 202   title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}},
 203   author={Pettie, S.},
 204   year={1999},
 205   publisher={University of Texas at Austin Austin, TX, USA}
 206 }
 207
 208 @article { karger:randomized,
 209    author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
 210    title = "{A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees}",
 211    journal = "Journal of the ACM",
 212    volume = "42",
 213    number = "2",
 214    pages = "321--328",
 215    year = "1995"
 216 }
 217
 218 @inproceedings { karger:sampling,
 219    title={Random sampling in matroids, with applications to graph connectivity and minimum spanning trees},
 220    author={Karger, D. R.},
 221    booktitle={FOCS '93: Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science},
 222    year={1993},
 223    pages={84--93}
 224 }
 225
 226 @article{ chan:backward,
 227   title={{Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees}},
 228   author={Chan, T. M.},
 229   journal={Information Processing Letters},
 230   volume={67},
 231   number={6},
 232   pages={303--304},
 233   year={1998},
 234 }
 235
 236 @article { frederickson:online,
 237    author = "Greg N. Frederickson",
 238    title = "{Data structures for on-line updating of minimum spanning trees}",
 239    journal = "{SIAM Journal on Computing}",
 240    volume = "14",
 241    pages = "781--798",
 242    year = "1985"
 243 }
 244
 245 @article { mm:mst,
 246    author = "Martin Mare\v{s}",
 247    title = "{Two linear time algorithms for MST on minor closed graph classes}",
 248    journal = "{Archivum Mathematicum}",
 249    volume = "40",
 250    pages = "315--320",
 251    year = "2004"
 252 }
 253
 254 @inproceedings{ mm:rank,
 255   author = "Martin Mare\v{s} and Milan Straka",
 256   title = "Linear-Time Ranking of Permutations",
 257   booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium",
 258   location = "Eilat, Israel, October 8--10, 2007",
 259   volume = "4698",
 260   series = "Lecture Notes in Computer Science",
 261   pages = "187--193",
 262   publisher = "Springer Verlag",
 263   year = "2007",
 264 }
 265
 266 @article{ ft:fibonacci,
 267  author = {Michael L. Fredman and Robert Endre Tarjan},
 268  title = {Fibonacci heaps and their uses in improved network optimization algorithms},
 269  journal = {Journal of the ACM},
 270  volume = {34},
 271  number = {3},
 272  year = {1987},
 273  issn = {0004-5411},
 274  pages = {596--615},
 275  doi = {http://doi.acm.org/10.1145/28869.28874},
 276  }
 277
 278 @article{ komlos:verify,
 279   author    = {J{\'a}nos Koml{\'o}s},
 280   title     = {Linear verification for spanning trees.},
 281   journal   = {Combinatorica},
 282   volume    = {5},
 283   number    = {1},
 284   year      = {1985},
 285   pages     = {57--65},
 286   bibsource = {DBLP, http://dblp.uni-trier.de}
 287 }
 288
 289 @inproceedings{ king:verify,
 290     author = "Valerie King",
 291     title = "A Simpler Minimum Spanning Tree Verification Algorithm",
 292     booktitle = "{Algorithms and Data Structures --- WADS '95: 4th International Workshop}",
 293     pages = "440--448",
 294     year = "1995",
 295     location = "Kingston, Canada",
 296     volume = "955",
 297     series = "Lecture Notes in Computer Science",
 298     publisher = "Springer Verlag",
 299     url = "citeseer.ist.psu.edu/king95simpler.html"
 300 }
 301
 302 @article{ king:verifytwo,
 303   title={{A Simpler Minimum Spanning Tree Verification Algorithm}},
 304   author={King, Valerie},
 305   journal={Algorithmica},
 306   volume={18},
 307   pages={263--270},
 308   year={1997}
 309 }
 310
 311 @book { schrijver,
 312     author = "Alexander Schrijver",
 313     title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
 314     series = "Algorithms and Combinatorics",
 315     volume = 24,
 316     year = 2003,
 317     publisher = "Springer Verlag"
 318 }
 319
 320 @inproceedings{ thorup:aczero,
 321  author = {Mikkel Thorup},
 322  title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
 323  booktitle = {SODA '03: Proceedings of the 14th annual ACM-SIAM Symposium on Discrete algorithms},
 324  year = {2003},
 325  isbn = {0-89871-538-5},
 326  pages = {699--707},
 327  location = {Baltimore, Maryland},
 328 }
 329
 330 @article{ kruskal:mst,
 331   title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
 332   author={Kruskal Jr, J. B.},
 333   journal={Proceedings of the American Mathematical Society},
 334   volume={7},
 335   number={1},
 336   pages={48--50},
 337   year={1956},
 338   publisher={JSTOR}
 339 }
 340
 341 @book{ diestel:gt,
 342   title={{Graph Theory}},
 343   author={Diestel, R.},
 344   year={2005},
 345   publisher={Springer Verlag}
 346 }
 347
 348 @article{ graham:msthistory,
 349   title={{On the history of the minimum spanning tree problem}},
 350   author={Graham, R. L. and Hell, P.},
 351   journal={Annals of the History of Computing},
 352   volume={7},
 353   number={1},
 354   pages={43--57},
 355   year={1985}
 356 }
 357
 358 @article{ cayley:trees,
 359   title={{A theorem on trees}},
 360   author={Cayley, Arthur},
 361   journal={Quarterly Journal of Mathematics},
 362   volume={23},
 363   year={1889},
 364   pages={376--378}
 365 }
 366
 367 @article{ dijkstra:mst,
 368   title={{A note on two problems in connexion with graphs}},
 369   author = "Dijkstra, E. W.",
 370   journal={Numerische Mathematik},
 371   volume={1},
 372   number={1},
 373   pages={269--271},
 374   year={1959},
 375   publisher={Springer Verlag}
 376 }
 377
 378 @article{ prim:mst,
 379   author = "Prim, R. C.",
 380   title = "Shortest connection networks and some generalizations",
 381   journal = "Bell System Technical Journal",
 382   volume = "36",
 383   year = "1957",
 384   pages={567--574},
 385 }
 386
 387 @article{ choquet:mst,
 388   title={{Etude de certains r{\'e}seaux de routes}},
 389   author={Choquet, Gustave},
 390   journal={Comptes-rendus de l'Académie des Sciences},
 391   volume={206},
 392   pages={310},
 393   year={1938},
 394   note={In French}
 395 }
 396
 397 @incollection { sollin:mst,
 398   title={{Le trace de canalisation}},
 399   author={Sollin, M.},
 400   booktitle={Programming, Games, and Transportation Networks},
 401   editor={Berge, C. and Ghouilla-Houri, A.},
 402   publisher={Wiley, New York},
 403   year={1965},
 404   note={In French}
 405 }
 406
 407 @article{ boyer:cutting,
 408   title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
 409   author={Boyer, J. M. and Myrvold, W. J.},
 410   journal={Journal of Graph Algorithms and Applications},
 411   volume={8},
 412   number={3},
 413   pages={241--273},
 414   year={2004}
 415 }
 416
 417 @inproceedings{ takaoka:twothree,
 418   title={{Theory of 2-3 Heaps}},
 419   author={Takaoka, T. and Christchurch, N. Z.},
 420   booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON '99},
 421   location={Tokyo, Japan},
 422   year={1999},
 423   pages={41--50},
 424   publisher={Springer Verlag},
 425   series={{Lecture Notes in Computer Science}},
 426   volume={1627}
 427 }
 428
 429 @inproceedings{ takaoka:trinomial,
 430   title={{Theory of Trinomial Heaps}},
 431   author={Takaoka, Tadao},
 432   booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
 433   location={Sydney, Australia},
 434   year={2000},
 435   pages={362--372},
 436   publisher={Springer Verlag},
 437   series={{Lecture Notes in Computer Science}},
 438   volume={1858}
 439 }
 440
 441 @book{ clrs,
 442   title={{Introduction to Algorithms}},
 443   author={Leiserson, C. E. and Rivest, R. L. and Cormen, T. H. and Stein, C.},
 444   year={2001},
 445   publisher={McGraw-Hill}
 446 }
 447
 448 @article{ pettie:onlineverify,
 449  author       = {Seth Pettie},
 450  title        = {An Inverse-{A}ckermann Type Lower Bound for Online
 451                  Minimum Spanning Tree Verification},
 452  journal      = {Combinatorica},
 453  volume       = {26},
 454  number       = {2},
 455  pages        = {207--230},
 456  year         = {2006},
 457 }
 458
 459 @inproceedings{ pettie:onlineverify-conf,
 460   author = "S. Pettie",
 461   title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
 462     tree verification problem",
 463   booktitle = "FOCS 2002: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science",
 464   year = "2002",
 465   url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
 466 }
 467
 468 @article{ dixon:verify,
 469     author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
 470     title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
 471     journal = "SIAM Journal of Computing",
 472     volume = "21",
 473     number = "6",
 474     pages = "1184-1192",
 475     year = "1992",
 476     url = "citeseer.ist.psu.edu/dixon92verification.html"
 477 }
 478
 479 @inproceedings{ pettie:minirand,
 480  author = {Seth Pettie and Vijaya Ramachandran},
 481  title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
 482  booktitle = {SODA '02: Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms},
 483  year = {2002},
 484  isbn = {0-89871-513-X},
 485  pages = {713--722},
 486  location = {San Francisco, California},
 487 }
 488
 489 @inproceedings{ buchsbaum:verify,
 490   title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
 491   author={Buchsbaum, A. L. and Kaplan, H. and Rogers, A. and Westbrook, J. R.},
 492   booktitle={STOC 1998: Proceedings of the 30th annual ACM Symposium on Theory of Computing},
 493   pages={279--288},
 494   year={1998},
 495 }
 496
 497 @article{ bacala:parametric,
 498   title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
 499   author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
 500   journal={Theoretical Computer Science},
 501   volume={181},
 502   number={1},
 503   pages={57--74},
 504   year={1997},
 505   publisher={Elsevier}
 506 }
 507
 508 @inproceedings{ katriel:cycle,
 509   author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
 510   title = "A practical minimum spanning tree algorithm using the cycle property",
 511   booktitle = "Algorithms --- ESA 2003: 11th European Symposium",
 512   number = "2832",
 513   series = "LNCS",
 514   pages = "679--690",
 515   publisher = "Springer Verlag",
 516   year = "2003",
 517   url = "citeseer.ist.psu.edu/katriel03practical.html"
 518 }
 519
 520 @article{ alstrup:nca,
 521   title={{Nearest Common Ancestors: A Survey and a new Distributed Algorithm}},
 522   author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
 523   journal={Proceedings of the 14th annual ACM Symposium on Parallel algorithms and architectures},
 524   pages={258--264},
 525   year={2002},
 526 }
 527
 528 @article{ gabow:mst,
 529   title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
 530   author={Gabow, H. N. and Galil, Z. and Spencer, T. and Tarjan, R. E.},
 531   journal={Combinatorica},
 532   volume={6},
 533   number={2},
 534   pages={109--122},
 535   year={1986},
 536   publisher={Springer Verlag}
 537 }
 538
 539 @Unpublished{ eisner:tutorial,
 540   author =       {Jason Eisner},
 541   title =        {{State-of-the-Art Algorithms for Minimum Spanning
 542                   Trees: A~Tutorial Discussion}},
 543   note =         {Manuscript available online (78 pages), University of Pennsylvania},
 544   year =         1997,
 545   url =          {http://cs.jhu.edu/~jason/papers/#ms97},
 546 }
 547
 548 @article{ aho:lca,
 549   title={{On finding lowest common ancestors in trees.}},
 550   author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
 551   journal={SIAM Journal on Computing},
 552   volume={5},
 553   pages={115--132},
 554   year={1976}
 555 }
 556
 557 @book{ knuth:fundalg,
 558  author = {Donald E. Knuth},
 559  title = {The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms},
 560  year = {1997},
 561  isbn = {0-201-89683-4},
 562  publisher = {Addison Wesley Longman Publishing Co., Inc.},
 563  address = {Redwood City, CA, USA},
 564 }
 565
 566 @book{ knuth:seminalg,
 567  author = {Donald E. Knuth},
 568  title = {The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical algorithms},
 569  year = {1997},
 570  isbn = {978-0-201-89684-8},
 571  publisher = {Addison Wesley Longman Publishing Co., Inc.},
 572  address = {Redwood City, CA, USA},
 573 }
 574
 575 @book{ knuth:sas,
 576   author = {Donald E. Knuth},
 577   title = {{The Art of Computer Programming, Volume 3 (2nd ed.): Sorting and Searching}},
 578   year = {1998},
 579   isbn = {978-0-201-89685-5},
 580   publisher = {Addison Wesley Longman Publishing Co., Inc.},
 581   address = {Redwood City, CA, USA},
 582 }
 583
 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},
 588  year = {1998},
 589  isbn = {3-540-64230-7},
 590  pages = {366--398},
 591 }
 592
 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},
 597  year = {1972},
 598  pages = {73--80},
 599  location = {Denver, Colorado, United States},
 600  doi = {http://doi.acm.org/10.1145/800152.804898},
 601 }
 602
 603 @book{ okasaki:funcds,
 604   author = {Chris Okasaki},
 605   title = {Purely Functional Data Structures},
 606   year = {1999},
 607   publisher = {Cambridge University Press}
 608 }
 609
 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},
 613   year = {2007},
 614   publisher = {Intel Corp.},
 615   xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
 616 }
 617
 618 @article{ hagerup:dd,
 619   title={{Deterministic Dictionaries}},
 620   author={Hagerup, T. and Miltersen, P. B. and Pagh, R.},
 621   journal={Journal of Algorithms},
 622   volume={41},
 623   number={1},
 624   pages={69--85},
 625   year={2001}
 626 }
 627
 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},
 632   volume={31},
 633   number={3},
 634   pages={538--544},
 635   year={1984},
 636 }
 637
 638 @book{ motwani:randalg,
 639   title={{Randomized Algorithms}},
 640   author={Motwani, R. and Raghavan, P.},
 641   year={1995},
 642   publisher={Cambridge University Press}
 643 }
 644
 645 @article{ fw:fusion,
 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},
 649   volume={47},
 650   number={3},
 651   pages={424--436},
 652   year={1993},
 653 }
 654
 655 @article{ han:detsort,
 656   title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}},
 657   author={Han, Y.},
 658   journal={Proceedings of the 34th annual ACM Symposium on Theory of Computing},
 659   pages={602--608},
 660   year={2002},
 661 }
 662
 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={Proceedings of the 43rd Symposium on Foundations of Computer Science},
 667   pages={135--144},
 668   year={2002},
 669 }
 670
 671 @article{ 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   journal={Proc. 12th IEEE Symp. Computer Arithmetic},
 675   pages={2--9},
 676   year={1995}
 677 }
 678
 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},
 683   year={1993}
 684 }
 685
 686 @article{ turan:succinct,
 687   title={{Succinct representation of graphs.}},
 688   author={Tur\'an, G.},
 689   journal={Discrete Applied Mathematics},
 690   volume={8},
 691   number={3},
 692   pages={289--294},
 693   year={1984}
 694 }
 695
 696 @book{ jones:haskell,
 697   title={{Haskell 98 Language and Libraries: The Revised Report}},
 698   author={Jones, P. and Simon, L.},
 699   year={2003},
 700   publisher={Cambridge University Press}
 701 }
 702
 703 @article{ mader:dens,
 704   title={{Homomorphieeigenschaften und mittlere Kantendichte von Graphen}},
 705   author={Mader, W.},
 706   journal={Mathematische Annalen},
 707   volume={174},
 708   number={4},
 709   pages={265--268},
 710   year={1967},
 711   publisher={Springer Verlag},
 712   note={In German}
 713 }
 714
 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",
 719     pages = "421-431",
 720     year = "1998",
 721     url = "citeseer.ist.psu.edu/223918.html"
 722 }
 723
 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},
 728   volume={79},
 729   number={6},
 730   pages={281--284},
 731   year={2001}
 732 }
 733
 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},
 738   pages = "99-106",
 739   year = "1997"
 740 }
 741
 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},
 746   volume={57},
 747   pages={75--83},
 748   year={1995}
 749 }
 750
 751 @article{ ruskey:hce,
 752   title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn}},
 753   author={Ruskey, F. and Savage, C. D.},
 754   journal={SIAM Journal on Discrete Mathematics},
 755   volume={6},
 756   number={1},
 757   pages={152--166},
 758   year={1993}
 759 }
 760
 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},
 765   volume={2},
 766   number={4},
 767   pages={227--268},
 768   year={1997}
 769 }
 770
 771 @book{ reingold:catp,
 772   title={{Combinatorial Algorithms: Theory and Practice}},
 773   author={Reingold, E. M.},
 774   year={1977},
 775   publisher={Prentice Hall College Div}
 776 }
 777
 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},
 782  year = {1989},
 783  isbn = {3-540-51542-9},
 784  pages = {39--46},
 785 }
 786
 787 @book { ss:fifteen,
 788   title={{The 15 Puzzle Book}},
 789   author={Slocum, J. and Sonneveld D.},
 790   year={2006},
 791   publisher={The Slocum Puzzle Foundation, Beverly Hills, CA, USA}
 792 }
 793
 794 @article{ rs:wagner,
 795   title={{Graph minors: XX. Wagner's Conjecture}},
 796   author={Robertson, N. and Seymour, P. D.},
 797   journal={Journal of Combinatorial Theory Series B},
 798   volume={92},
 799   number={2},
 800   pages={325--357},
 801   year={2004},
 802 }
 803
 804 @book{ matnes:idm,
 805   title={{Invitation to Discrete Mathematics}},
 806   author={Matou{\v{s}}ek, J. and Ne{\v{s}}et{\v{r}}il, J.},
 807   year={1998},
 808   publisher={Oxford University Press}
 809 }
 810
 811 @article{ stanley:econe,
 812   title={{Enumerative combinatorics. Vol. 1}},
 813   author={Stanley, R. P.},
 814   journal={Cambridge Studies in Advanced Mathematics},
 815   volume={49},
 816   year={1997}
 817 }
 818
 819 @article{ kaplansky:rooks,
 820   title={{The problem of the rooks and its applications}},
 821   author={Kaplansky, I. and Riordan, J.},
 822   journal={Duke Mathematical Journal},
 823   volume={13},
 824   number={2},
 825   pages={259--268},
 826   year={1946}
 827 }
 828
 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.},
 833   volume = {11},
 834   year = {1970},
 835   pages = {1277--1280}
 836 }
 837
 838 @article{ even:dinic,
 839   author = {Shimon Even and Robert Endre Tarjan},
 840   title = {Network Flow and Testing Graph Connectivity},
 841   publisher = {SIAM},
 842   year = {1975},
 843   journal = {SIAM Journal on Computing},
 844   volume = {4},
 845   number = {4},
 846   pages = {507--518},
 847   url = {http://link.aip.org/link/?SMJ/4/507/1},
 848   doi = {10.1137/0204043}
 849 }
 850
 851 @article{ valiant:permanent,
 852   title={{The complexity of computing the permanent}},
 853   author={Valiant, L. G.},
 854   journal={Theoretical Computer Science},
 855   volume={8},
 856   number={2},
 857   pages={189--201},
 858   year={1979}
 859 }
 860
 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},
 865   volume={51},
 866   number={4},
 867   pages={671--697},
 868   year={2004}
 869 }
 870
 871 @article{ kasteleyn:crystals,
 872   title={{Graph theory and crystal physics}},
 873   author={Kasteleyn, P. W.},
 874   journal={Graph Theory and Theoretical Physics},
 875   publisher={Academic Press, London},
 876   pages={43--110},
 877   year={1967}
 878 }
 879
 880 @article{ yuster:matching,
 881   title={{Maximum matching in graphs with an excluded minor}},
 882   author={Yuster, R. and Zwick, U.},
 883   journal={SODA 2007: Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms},
 884   pages={108--117},
 885   year={2007},
 886 }
 887
 888 @article{ mucha:matching,
 889   title={{Maximum Matchings in Planar Graphs via Gaussian Elimination}},
 890   author={Mucha, M. and Sankowski, P.},
 891   journal={Algorithmica},
 892   volume={45},
 893   number={1},
 894   pages={3--20},
 895   year={2006},
 896 }
 897
 898 @article {lovasz:minors,
 899   title={{Graph Minor Theory}},
 900   author={Lov\'asz, L.},
 901   journal={Bulletin of the American Mathematical Society},
 902   volume={43},
 903   number={1},
 904   pages={75--86},
 905   year={2005}
 906 }
 907
 908 @article{ andersson:fusion,
 909   title={{Fusion trees can be implemented with AC$^0$ instructions only}},
 910   author={Andersson, A. and Miltersen, P. B. and Thorup, M.},
 911   journal={Theoretical Computer Science},
 912   volume={215},
 913   number={1-2},
 914   pages={337--344},
 915   year={1999},
 916   publisher={Elsevier}
 917 }
 918
 919 @article{ thorup:rampq,
 920   title={{On RAM priority queues}},
 921   author={THORUP, M.},
 922   journal={SIAM Journal on Computing},
 923   volume={30},
 924   number={1},
 925   pages={86--109},
 926   year={2001},
 927 }
 928
 929 @article{ thorup:pqsssp,
 930   title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
 931   author={Thorup, M.},
 932   journal={STOC 2003: Proceedings of the 35th ACM Symposium on Theory of Computing},
 933   pages={149--158},
 934   year={2003},
 935 }
 936
 937 @article{ chazelle:mstapprox,
 938   title={{Approximating the Minimum Spanning Tree Weight in Sublinear Time}},
 939   author={Chazelle, B. and Rubinfeld, R. and Trevisan, L.},
 940   journal={SIAM Journal on Computing},
 941   volume={34},
 942   pages={1370},
 943   year={2005},
 944 }
 945
 946 @inproceedings{ czumaj:metric,
 947  author = {Artur Czumaj and Christian Sohler},
 948  title = {Estimating the weight of metric minimum spanning trees in sublinear-time},
 949  booktitle = {STOC '04: Proceedings of the 36th annual ACM Symposium on Theory of Computing},
 950  year = {2004},
 951  isbn = {1-58113-852-0},
 952  pages = {175--183},
 953  location = {Chicago, IL, USA},
 954 }
 955
 956 @inproceedings{ czumaj:euclidean,
 957  author = {Artur Czumaj and Funda Erg\"{u}n and Lance Fortnow and Avner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler},
 958  title = {Sublinear-time approximation of Euclidean minimum spanning tree},
 959  booktitle = {SODA '03: Proceedings of the 14th annual ACM-SIAM Symposium on Discrete Algorithms},
 960  year = {2003},
 961  isbn = {0-89871-538-5},
 962  pages = {813--822},
 963  publisher = {Society for Industrial and Applied Mathematics},
 964 }
 965
 966 @book{ ieee:binfp,
 967   author = {IEEE},
 968   title = {IEEE Standard 754-1985 for Binary Floating-point Arithmetic},
 969   year = {1985},
 970   publisher = {IEEE}
 971 }
 972
 973 @article{ dgoldberg:fp,
 974   title={{What every computer scientist should know about floating-point arithmetic}},
 975   author={Goldberg, D.},
 976   journal={ACM Computing Surveys},
 977   volume={23},
 978   number={1},
 979   pages={5--48},
 980   year={1991},
 981 }
 982
 983 @article{ thorup:floatint,
 984   title={{Floats, Integers, and Single Source Shortest Paths}},
 985   author={Thorup, M.},
 986   journal={Journal of Algorithms},
 987   volume={35},
 988   number={2},
 989   pages={189--201},
 990   year={2000},
 991 }
 992
 993 @article{ shamos:closest,
 994   title={{Closest-point problems}},
 995   author={Shamos, M. I. and Hoey, D.},
 996   journal={Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science},
 997   pages={151--162},
 998   year={1975}
 999 }
1000
1001 @article{ fortune:voronoi,
1002   title={{A sweepline algorithm for Voronoi diagrams}},
1003   author={Fortune, S.},
1004   journal={Algorithmica},
1005   volume={2},
1006   number={1},
1007   pages={153--174},
1008   year={1987},
1009 }
1010
1011 @article{ zhou:nodel,
1012   title={{Efficient minimum spanning tree construction without Delaunay triangulation}},
1013   author={Zhou, H. and Shenoy, N. and Nicholls, W.},
1014   journal={Information Processing Letters},
1015   volume={81},
1016   number={5},
1017   pages={271--276},
1018   year={2002},
1019 }
1020
1021 @techreport{ eppstein:spanning,
1022   title={{Spanning Trees and Spanners}},
1023   author={Eppstein, D.},
1024   year={1996},
1025   institution={Information and Computer Science, University of California, Irvine},
1026   number = {96-16},
1027 }
1028
1029 @article{ garey:steiner,
1030   title={{The Complexity of Computing Steiner Minimal Trees}},
1031   author={Garey, M. R. and Graham, R. L. and Johnson, D. S.},
1032   journal={SIAM Journal on Applied Mathematics},
1033   volume={32},
1034   number={4},
1035   pages={835--859},
1036   year={1977},
1037 }
1038
1039 @article{ garey:rectisteiner,
1040   title={{The Rectilinear Steiner Tree Problem is NP-Complete}},
1041   author={Garey, M. R. and Johnson, D. S.},
1042   journal={SIAM Journal on Applied Mathematics},
1043   volume={32},
1044   number={4},
1045   pages={826--834},
1046   year={1977},
1047 }
1048
1049 @article{ proemel:steiner,
1050   title={{A new approximation algorithm for the Steiner tree problem with performance ratio $5/3$}},
1051   author={Promel, H. J. and Steger, A.},
1052   journal={Journal of Algorithms},
1053   volume={36},
1054   pages={89--101},
1055   year={2000}
1056 }
1057
1058 @article{ arora:tspapx,
1059   title={{Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems}},
1060   author={Arora, S.},
1061   journal={Journal of the ACM},
1062   volume={45},
1063   number={5},
1064   pages={753--782},
1065   year={1998},
1066 }
1067
1068 @article{ harel:nca,
1069   title={{Fast algorithms for finding nearest common ancestors}},
1070   author={Harel, D. and Tarjan, R. E.},
1071   journal={SIAM Journal on Computing},
1072   volume={13},
1073   number={2},
1074   pages={338--355},
1075   year={1984},
1076 }
1077
1078 @article{ gomoryhu,
1079    author = "R. E. Gomory and T. C. Hu",
1080    title = "Multi-Terminal Network Flows",
1081    journal = "{Journal of SIAM}",
1082    volume = {9},
1083    number = {4},
1084    year = {1961},
1085    pages = {551--570}
1086 }
1087
1088 @inproceedings{ bhalgat:ght,
1089  author = {Ramesh Hariharan and Telikepalli Kavitha and Debmalya Panigrahi and Anand Bhalgat},
1090  title = {{An $\widehat\O(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs}},
1091  booktitle = {STOC '07: Proceedings of the 39th annual ACM Symposium on Theory of Computing},
1092  year = {2007},
1093  isbn = {978-1-59593-631-8},
1094  pages = {605--614},
1095  location = {San Diego, California, USA},
1096  doi = {http://doi.acm.org/10.1145/1250790.1250879},
1097 }
1098
1099 @article{ sleator:trees,
1100   title={{A data structure for dynamic trees}},
1101   author={Sleator, D. D. and Tarjan, R. E.},
1102   journal={Journal of Computer and System Sciences},
1103   volume={26},
1104   number={3},
1105   pages={362--391},
1106   year={1983},
1107 }
1108
1109 @article{ chernoff,
1110   title={{A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations}},
1111   author={Chernoff, H.},
1112   journal={The Annals of Mathematical Statistics},
1113   volume={23},
1114   number={4},
1115   pages={493--507},
1116   year={1952},
1117   publisher={JSTOR}
1118 }
1119
1120 @article{ pettie:parallel,
1121  author       = {Seth Pettie and Vijaya Ramachandran},
1122  title        = {A randomized time-work optimal parallel algorithm for
1123                  finding a minimum spanning forest},
1124  journal      = {SIAM Journal of Computing},
1125  volume       = {31},
1126  number       = {6},
1127  year         = {2002},
1128  pages        = {1879--1895},
1129 }
1130
1131 @article{ chazelle:softheap,
1132  author = {Bernard Chazelle},
1133  title = {The soft heap: an approximate priority queue with optimal error rate},
1134  journal = {Journal of the ACM},
1135  volume = {47},
1136  number = {6},
1137  year = {2000},
1138  issn = {0004-5411},
1139  pages = {1012--1027},
1140  doi = {http://doi.acm.org/10.1145/355541.355554},
1141 }
1142
1143 @article{ propp:randommst,
1144  author = {James Gary Propp and David Bruce Wilson},
1145  title = {How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph},
1146  journal = {Journal of Algorithms},
1147  volume = {27},
1148  number = {2},
1149  year = {1998},
1150  issn = {0196-6774},
1151  pages = {170--217},
1152  doi = {http://dx.doi.org/10.1006/jagm.1997.0917},
1153 }
1154
1155 @article{ vuillemin:binheap,
1156   title={{A Data Structure for Manipulating Priority Queues}},
1157   author={Vuillemin, Jean},
1158   journal={Communications of the ACM},
1159   volume = 21,
1160   number = 4,
1161   pages={309--315},
1162   year={1978}
1163 }
1164
1165 @article{ hoare:qsort,
1166   title={{Quicksort}},
1167   author={Hoare, Charles Anthony Richard},
1168   journal={The Computer Journal},
1169   volume={5},
1170   number={1},
1171   pages={10--16},
1172   year={1962},
1173   publisher={British Computer Society}
1174 }
1175
1176 @article{ blum:selection,
1177   title={{Time bounds for selection}},
1178   author={Blum, M. and Floyd, R. W. and Pratt, V. and Rivest, R. L. and Tarjan, R. E.},
1179   journal={Journal of Computer and System Sciences},
1180   volume={7},
1181   number={4},
1182   pages={448--461},
1183   year={1973}
1184 }
1185
1186 @article{ hoare:qselect,
1187  author = {Hoare, Charles Anthony Richard},
1188  title = {Algorithm 65: find},
1189  journal = {Communications of the ACM},
1190  volume = {4},
1191  number = {7},
1192  year = {1961},
1193  issn = {0001-0782},
1194  pages = {321--322},
1195  doi = {http://doi.acm.org/10.1145/366622.366647},
1196 }
1197
1198 @article{ dinitz:treeiso,
1199   title={{On an algorithm of Zemlyachenko for subtree isomorphism}},
1200   author={Dinitz, Y. and Itai, A. and Rodeh, M.},
1201   journal={Information Processing Letters},
1202   volume={70},
1203   number={3},
1204   pages={141--146},
1205   year={1999},
1206 }
1207
1208 @inproceedings{ zemlay:treeiso,
1209   title={{Determining tree isomorphism}},
1210   author={Zemlayachenko, V. N.},
1211   booktitle={{Voprosy Kibernetiki, Proceedings of the Seminar on Combinatorial Mathematics}},
1212   location={Moscow 1971},
1213   publisher={{Scientific Council of the Complex Problem ``Kibernetika'', Akad. Nauk SSSR}},
1214   year={1973},
1215   pages={54--60},
1216   note={In Russian},
1217 }
1218
1219 @inproceedings{ alstrup:marked,
1220   title={{Marked ancestor problems}},
1221   author={Alstrup, S. and Husfeldt, T. and Rauhe, T.},
1222   booktitle={FOCS '98: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science},
1223   pages={534--543},
1224   year={1998}
1225 }
1226
1227 @inproceedings{ arvind:isomorph,
1228   title={{Graph isomorphism is in SPP}},
1229   author={Arvind, V. and Kurur, P. P.},
1230   booktitle={FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science},
1231   pages={743--750},
1232   year={2002}
1233 }
1234
1235 @article{ ackermann:function,
1236   title={{Zum Hilbertschen Aufbau der reellen Zahlen}},
1237   author={Ackermann, W.},
1238   journal={Mathematische Annalen},
1239   volume={99},
1240   number={1},
1241   pages={118--133},
1242   year={1928},
1243   publisher={Springer},
1244   notes={In German}
1245 }
1246
1247 @article{ klazar:gdss,
1248   title={{Generalized Davenport--Schinzel Sequences: Results, problems, and applications}},
1249   author={Klazar, M.},
1250   journal={INTEGERS: The Electronic Journal of Combinatorial Number Theory},
1251   volume={2},
1252   number={A11},
1253   pages={2},
1254   year={2002}
1255 }
1256
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},
1261   year = {1989},
1262   isbn = {0-89791-307-8},
1263   pages = {345--354},
1264   location = {Seattle, Washington, United States},
1265   doi = {http://doi.acm.org/10.1145/73007.73040},
1266 }
1267
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},
1272   volume={46},
1273   number={4},
1274   pages={502--516},
1275   year={1999}
1276 }
1277
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},
1282   volume={48},
1283   number={4},
1284   pages={723--760},
1285   year={2001},
1286 }
1287
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},
1292   volume={14},
1293   pages={781--798},
1294   year={1985}
1295 }
1296
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},
1301   volume={44},
1302   number={5},
1303   pages={669--696},
1304   year={1997},
1305 }
1306
1307 @article{ henzinger:mst,
1308   title={{Maintaining minimum spanning trees in dynamic graphs}},
1309   author={Henzinger, M. R. and King, V.},
1310   journal={ICALP '97: Proceedings of the 24th International Colloquium on Automata, Languages and Programming},
1311   pages={594--604},
1312   year={1997},
1313 }
1314
1315 @mastersthesis { mares:dga,
1316   title={{Dynamick\'e grafov\'e algoritmy}},
1317   author={Martin Mare\v{s}},
1318   school={Charles University in Prague, Faculty of Math and Physics},
1319   year={2000},
1320   notes={In Czech}
1321 }
1322
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},
1329   year = {1997},
1330   url = {http://gatekeeper.dec.com/pub/DEC/SRC/technical-notes/abstracts/src-tn-1997-004.html}
1331 }
1332
1333 @book{ overmars:ds,
1334   author = {Mark H. Overmars},
1335   title = {Design of Dynamic Data Structures},
1336   year = {1987},
1337   isbn = {038712330X},
1338   publisher = {Springer Verlag},
1339   series={{Lecture Notes in Computer Science}},
1340   volume={156}
1341 }
1342
1343 @article{ eppstein:ksmallest,
1344   title={{Finding the $k$~Smallest Spanning Trees}},
1345   author={Eppstein, D.},
1346   journal={BIT},
1347   volume={32},
1348   number={2},
1349   pages={237--248},
1350   year={1992},
1351   publisher={Springer Verlag}
1352 }
1353
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},
1358   volume={10},
1359   pages={247},
1360   year={1981},
1361 }
1362
1363 @inproceedings{ thorup:nearopt,
1364  author = {Mikkel Thorup},
1365  title = {Near-optimal fully-dynamic graph connectivity},
1366  booktitle = {STOC '00: Proceedings of the 32nd annual ACM Symposium on Theory of Computing},
1367  year = {2000},
1368  isbn = {1-58113-184-4},
1369  pages = {343--350},
1370  location = {Portland, Oregon, United States},
1371  doi = {http://doi.acm.org/10.1145/335305.335345},
1372 }
1373
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},
1378   volume={22},
1379   number={3},
1380   pages={351--362},
1381   year={1998},
1382 }
1383
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},
1388   volume={46},
1389   number={3},
1390   pages={362--394},
1391   year={1999}
1392 }
1393
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},
1398   volume = {69},
1399   number = {3},
1400   year = {2004},
1401   issn = {0022-0000},
1402   pages = {330--353},
1403   doi = {http://dx.doi.org/10.1016/j.jcss.2004.04.003},
1404 }
1405
1406 @inproceedings{ hagerup:sssp,
1407   author = {Torben Hagerup},
1408   title = {{Improved Shortest Paths on the Word RAM}},
1409   booktitle = {ICALP '00: Proceedings of the 27th International Colloquium on Automata, Languages and Programming},
1410   year = {2000},
1411   isbn = {3-540-67715-1},
1412   pages = {61--72},
1413 }
1414
1415 @techreport { hakmem,
1416     author = "Beeler, Michael and Gosper, R. William and Schroeppel, Rich",
1417     title = "{HAKMEM}",
1418     institution = "Massachusetts Institute of Technology",
1419     year = "1972",
1420     number = "239",
1421     type = "Memo"
1422 }
1423
1424 @book{ oxley:matroids,
1425   title={{Matroid Theory}},
1426   author={Oxley, J. G.},
1427   year={1992},
1428   publisher={Oxford University Press}
1429 }
1430
1431 @article{ katoh:kmin,
1432   author = {N. Katoh and T. Ibaraki and H. Mine},
1433   title = {An Algorithm for Finding $K$ Minimum Spanning Trees},
1434   year = {1981},
1435   journal = {SIAM Journal on Computing},
1436   volume = {10},
1437   number = {2},
1438   pages = {247--255},
1439 }
1440
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},
1445   volume = {48},
1446   number = {2},
1447   year = {2001},
1448   issn = {0004-5411},
1449   pages = {297--323},
1450   doi = {http://doi.acm.org/10.1145/375827.375847},
1451 }
1452
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},
1457   year={1994},
1458   publisher={American Mathematical Society}
1459 }
1460
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},
1465   volume={1},
1466   number={1},
1467   pages={111--129},
1468   year={1986},
1469 }
1470
1471 @article{ 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},
1475   volume = {00},
1476   year = {2005},
1477   isbn = {0-7695-2468-0},
1478   pages = {174-183},
1479   doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.75},
1480 }
1481
1482 @book{ jaja:parallel,
1483   title={{An introduction to parallel algorithms}},
1484   author={J{\'a}J{\'a}, J.},
1485   year={1992},
1486   publisher={Addison Wesley Longman Publishing Co., Inc. Redwood City, CA, USA}
1487 }
1488
1489 @techreport { mm:ga,
1490   author = "Martin Mare\v{s}",
1491   title = "{Krajinou grafov\'ych algoritm\accent23u}",
1492   institution = "Institut Teoretick\'e Informatiky",
1493   address = "Praha, Czech Republic",
1494   year = "2007",
1495   number = "2007--330",
1496   type = "ITI series",
1497   note = {In Czech},
1498 }
1499
1500 @book { horak:mofivefour,
1501   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},
1502   title = {54.~ro\v{c}n\'\i{}k matematick\'e olympi\'ady na st\v{r}edn\'\i{}ch \v{s}kol\'ach},
1503   publisher = {Jednota \v{c}esk\'ych matematik\accent23u a fyzik\accent23u},
1504   address = {Praha},
1505   year = {2007},
1506   note = {In Czech},
1507   isbn = {80-7015-109-9},
1508 }
1509
1510 @article{ tarjan:applpc,
1511  author = {Robert Endre Tarjan},
1512  title = {Applications of Path Compression on Balanced Trees},
1513  journal = {Journal of the ACM},
1514  volume = {26},
1515  number = {4},
1516  year = {1979},
1517  issn = {0004-5411},
1518  pages = {690--715},
1519  doi = {http://doi.acm.org/10.1145/322154.322161},
1520 }
1521
1522 @article{ kostochka:lbh,
1523   title={{Lower bound of the hadwiger number of graphs by their average degree}},
1524   author={Kostochka, A. V.},
1525   journal={Combinatorica},
1526   volume={4},
1527   number={4},
1528   pages={307--316},
1529   year={1984},
1530 }
1531
1532 @article{ thomason:efc,
1533   title={{An extremal function for contractions of graphs}},
1534   author={Thomason, A.},
1535   journal={Mathematical proceedings of the Cambridge Philosophical Society},
1536   volume={95},
1537   number={2},
1538   pages={261--265},
1539   year={1984},
1540   publisher={Cambridge University Press}
1541 }