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