biblio.bib

   1 @inproceedings{ bender:lca,
   2     author = "Michael A. Bender and Martin Farach-Colton",
   3     title = "The {LCA} Problem Revisited",
   4     booktitle = "Latin American Theoretical {INformatics}",
   5     pages = "88--94",
   6     year = "2000",
   7     url = "citeseer.ist.psu.edu/bender00lca.html" }
   8
   9 @inproceedings{ frederickson91ambivalent,
  10     author = "Greg N. Frederickson",
  11     title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
  12     booktitle = "{IEEE} Symposium on Foundations of Computer Science",
  13     pages = "632--641",
  14     year = "1991",
  15     url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" }
  16
  17 @article{ tarjan:wcsetunion,
  18  author = {Robert E. Tarjan and Jan van Leeuwen},
  19  title = {Worst-case Analysis of Set Union Algorithms},
  20  journal = {J. ACM},
  21  volume = {31},
  22  number = {2},
  23  year = {1984},
  24  issn = {0004-5411},
  25  pages = {245--281},
  26  doi = {http://doi.acm.org/10.1145/62.2160},
  27  publisher = {ACM Press},
  28  address = {New York, NY, USA},
  29 }
  30
  31 @article{ tarjan:setunion,
  32   title={{Efficiency of a Good But Not Linear Set Union Algorithm}},
  33   author={Tarjan, R.E.},
  34   journal={Journal of the ACM},
  35   volume={22},
  36   number={2},
  37   pages={215--225},
  38   year={1975},
  39   publisher={ACM Press New York, NY, USA}
  40 }
  41
  42 @inproceedings { fw:transdich,
  43    author = "M. Fredman and D. E. Willard",
  44    title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}",
  45    booktitle = "{Proceedings of FOCS'90}",
  46    pages = "719--725",
  47    year = "1990"
  48 }
  49
  50 @article{ boas:vebt,
  51   author    = {Peter van Emde Boas},
  52   title     = {Preserving Order in a Forest in Less Than Logarithmic Time
  53                and Linear Space.},
  54   journal   = {Inf. Process. Lett.},
  55   volume    = {6},
  56   number    = {3},
  57   year      = {1977},
  58   pages     = {80-82},
  59   bibsource = {DBLP, http://dblp.uni-trier.de}
  60 }
  61
  62 @article{ benamram:pm,
  63     author = "Ben-Amram, Amir M.",
  64     title = "What is a ``Pointer Machine''?",
  65     journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
  66     volume = "26",
  67     year = "1995",
  68     url = "citeseer.ist.psu.edu/ben-amram95what.html" }
  69
  70 @article{ matsui:planar,
  71     author = "Tomomi Matsui",
  72     title = "{The Minimum Spanning tree Problem on a Planar Graph}",
  73     journal = "Discrete Applied Mathematics",
  74     volume = "58",
  75     year = "1995",
  76     pages = "91--94",
  77     url = "citeseer.nj.nec.com/2319.html"
  78 }
  79
  80 @article{ chazelle:ackermann,
  81     author = "Bernard Chazelle",
  82     title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
  83     journal = jacm,
  84     volume = "47",
  85     pages = "1028--1047",
  86     year = "2000"
  87 }
  88
  89 @article{ chazelle:almostacker,
  90   title={{A faster deterministic algorithm for minimum spanning trees}},
  91   author={Chazelle, B.},
  92   journal={Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS'97)},
  93   pages={22},
  94   year={1997},
  95   publisher={IEEE Computer Society Washington, DC, USA}
  96 }
  97
  98 @article{ nesetril:history,
  99     author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
 100     title = "{Some remarks on the history of MST-problem}",
 101     journal = "Archivum Mathematicum",
 102     volume = "33",
 103     pages = "15--22",
 104     year = "1997"
 105 }
 106
 107 @article{ nesetril:boruvka,
 108     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
 109     title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
 110     journal = "Discrete Mathematics",
 111     volume = "233(1--3)",
 112     pages = "3--36",
 113     year = "2001"
 114 }
 115
 116 @incollection { nesetril:minors,
 117     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
 118     title = "{Colorings and Homomorphisms of Minor Closed Classes}",
 119     booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
 120     editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
 121     year = "2003",
 122     pages = "651--664",
 123     publisher = "Springer Verlag"
 124 }
 125
 126 @article { boruvka:ojistem,
 127     author = "Otakar Bor{\accent23u}vka",
 128     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
 129     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
 130     volume = "III",
 131     year = "1926",
 132     pages = "37--58",
 133     note = "In Czech with German summary"
 134 }
 135
 136 @article { boruvka:networks,
 137     author = "Otakar Bor{\accent23u}vka",
 138     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)}",
 139     journal = "Elektronick\'y obzor",
 140     volume = "15",
 141     year = "1926",
 142     pages = "153--154",
 143     note = "In Czech"
 144 }
 145
 146 @article { jarnik:ojistem,
 147     author = "Vojt\v{e}ch Jarn\'\i{}k",
 148     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
 149     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
 150     volume = "VI",
 151     year = "1930",
 152     pages = "57--63",
 153     note = "In Czech"
 154 }
 155
 156 @book { tarjan:dsna,
 157     author = "Robert E. Tarjan",
 158     title = "{Data structures and network algorithms}",
 159     series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}",
 160     volume = 44,
 161     year = "1983",
 162     publisher = "SIAM"
 163 }
 164
 165 @article { gh:history,
 166     author = "R. L. Graham and P. Hell",
 167     title = "{On the history of the minimum spanning tree problem}",
 168     journal = "{Annals of the History of Computing}",
 169     volume = "7",
 170     year = "1985",
 171     pages = "43--57"
 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    publisher = "Springer Verlag",
 199    pages = "49--60"
 200 }
 201
 202 @article { pettie:alpha,
 203   title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}},
 204   author={Pettie, S.},
 205   year={1999},
 206   publisher={University of Texas at Austin Austin, TX, USA}
 207 }
 208
 209 @article { karger:randomized,
 210    author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
 211    title = "{A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees}",
 212    journal = jacm,
 213    volume = "42",
 214    number = "2",
 215    pages = "321--328",
 216    year = "1995"
 217 }
 218
 219 @inproceedings { karger:sampling,
 220    title={Random sampling in matroids, with applications to graph connectivity and minimum spanning trees},
 221    author={Karger, D.R.},
 222    booktitle={Proceedings of the 34th Annual Symposium on Foundations of Computer Science},
 223    year={1993},
 224    pages={84--93}
 225 }
 226
 227 @article{ chan:backward,
 228   title={{Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees}},
 229   author={Chan, T.M.},
 230   journal={Information Processing Letters},
 231   volume={67},
 232   number={6},
 233   pages={303--304},
 234   year={1998},
 235   publisher={Elsevier}
 236 }
 237
 238 @article { frederickson:online,
 239    author = "Greg N. Frederickson",
 240    title = "{Data structures for on-line updating of minimum spanning trees}",
 241    journal = "{SIAM Journal on Computing}",
 242    volume = "14",
 243    pages = "781--798",
 244    year = "1985"
 245 }
 246
 247 @article { mm:mst,
 248    author = "Martin Mare\v{s}",
 249    title = "{Two linear time algorithms for MST on minor closed graph classes}",
 250    journal = "{Archivum Mathematicum}",
 251    volume = "40",
 252    pages = "315--320",
 253    year = "2004"
 254 }
 255
 256 @inproceedings{ mm:rank,
 257   author = "Martin Mare\v{s} and Milan Straka",
 258   title = "Linear-Time Ranking of Permutations",
 259   booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium",
 260   location = "Eilat, Israel, October 8--10, 2007",
 261   volume = "4698",
 262   series = "Lecture Notes in Computer Science",
 263   pages = "187--193",
 264   publisher = "Springer",
 265   year = "2007",
 266 }
 267
 268 @article{ ft:fibonacci,
 269  author = {Michael L. Fredman and Robert Endre Tarjan},
 270  title = {Fibonacci heaps and their uses in improved network optimization algorithms},
 271  journal = {J. ACM},
 272  volume = {34},
 273  number = {3},
 274  year = {1987},
 275  issn = {0004-5411},
 276  pages = {596--615},
 277  doi = {http://doi.acm.org/10.1145/28869.28874},
 278  publisher = {ACM Press},
 279  address = {New York, NY, USA},
 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 fourteenth 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 Berlin and Heidelberg GmbH \& Co.}
 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={Quart. J. Math},
 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 J. Comput.",
 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 thirteenth 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 @article{ 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   journal={Proceedings of the thirtieth annual ACM Symposium on Theory of Computing},
 496   pages={279--288},
 497   year={1998},
 498   publisher={ACM Press New York, NY, USA}
 499 }
 500
 501 @article{ bacala:parametric,
 502   title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
 503   author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
 504   journal={Theoretical Computer Science},
 505   volume={181},
 506   number={1},
 507   pages={57--74},
 508   year={1997},
 509   publisher={Elsevier}
 510 }
 511
 512 @inproceedings{ katriel:cycle,
 513   author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
 514   title = "A practical minimum spanning tree algorithm using the cycle property",
 515   booktitle = "11th European Symposium on Algorithms (ESA)",
 516   number = "2832",
 517   series = "LNCS",
 518   pages = "679--690",
 519   publisher = "Springer",
 520   year = "2003",
 521   url = "citeseer.ist.psu.edu/katriel03practical.html"
 522 }
 523
 524 @article{ alstrup:nca,
 525   title={{Nearest common ancestors: a survey and a new distributed algorithm}},
 526   author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
 527   journal={Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures},
 528   pages={258--264},
 529   year={2002},
 530   publisher={ACM Press New York, NY, USA}
 531 }
 532
 533 @article{ gabow:mst,
 534   title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
 535   author={Gabow, H.N. and Galil, Z. and Spencer, T. and Tarjan, R.E.},
 536   journal={Combinatorica},
 537   volume={6},
 538   number={2},
 539   pages={109--122},
 540   year={1986},
 541   publisher={Springer}
 542 }
 543
 544 @Unpublished{ eisner:tutorial,
 545   author =       {Jason Eisner},
 546   title =        {State-of-the-Art Algorithms for Minimum Spanning
 547                   Trees: A Tutorial Discussion},
 548   note =         {Manuscript available online (78 pages), University of Pennsylvania},
 549   year =         1997,
 550   url =          {http://cs.jhu.edu/~jason/papers/#ms97},
 551 }
 552
 553 @article{ aho:lca,
 554   title={{On finding lowest common ancestors in trees.}},
 555   author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
 556   journal={SIAM Journal on Computing},
 557   volume={5},
 558   pages={115--132},
 559   year={1976}
 560 }
 561
 562 @book{ knuth:fundalg,
 563  author = {Donald E. Knuth},
 564  title = {The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms},
 565  year = {1997},
 566  isbn = {0-201-89683-4},
 567  publisher = {Addison Wesley Longman Publishing Co., Inc.},
 568  address = {Redwood City, CA, USA},
 569 }
 570
 571 @book{ knuth:seminalg,
 572  author = {Donald E. Knuth},
 573  title = {The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical algorithms},
 574  year = {1997},
 575  isbn = {978-0-201-89684-8},
 576  publisher = {Addison Wesley Longman Publishing Co., Inc.},
 577  address = {Redwood City, CA, USA},
 578 }
 579
 580 @book{ knuth:sas,
 581   author = {Donald E. Knuth},
 582   title = {{The Art of Computer Programming, Volume 3 (2nd ed.): Sorting and Searching}},
 583   year = {1998},
 584   isbn = {978-0-201-89685-5},
 585   publisher = {Addison Wesley Longman Publishing Co., Inc.},
 586   address = {Redwood City, CA, USA},
 587 }
 588
 589 @inproceedings{ hagerup:wordram,
 590  author = {Torben Hagerup},
 591  title = {{Sorting and Searching on the Word RAM}},
 592  booktitle = {STACS '98: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science},
 593  year = {1998},
 594  isbn = {3-540-64230-7},
 595  pages = {366--398},
 596  publisher = {Springer-Verlag},
 597  address = {London, UK},
 598 }
 599
 600 @inproceedings{ cook:ram,
 601  author = {Stephen A. Cook and Robert A. Reckhow},
 602  title = {Time-bounded random access machines},
 603  booktitle = {STOC '72: Proceedings of the fourth annual ACM Symposium on Theory of Computing},
 604  year = {1972},
 605  pages = {73--80},
 606  location = {Denver, Colorado, United States},
 607  doi = {http://doi.acm.org/10.1145/800152.804898},
 608  publisher = {ACM},
 609  address = {New York, NY, USA},
 610 }
 611
 612 @book{ okasaki:funcds,
 613   author = {Chris Okasaki},
 614   title = {Purely Functional Data Structures},
 615   year = {1999},
 616   publisher = {Cambridge University Press}
 617 }
 618
 619 @book { intel:pentium,
 620   author = {{Intel Corp.}},
 621   title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference},
 622   year = {2007},
 623   publisher = {Intel Corp.},
 624   xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
 625 }
 626
 627 @article{ hagerup:dd,
 628   title={{Deterministic Dictionaries}},
 629   author={Hagerup, T. and Miltersen, P.B. and Pagh, R.},
 630   journal={J. Algorithms},
 631   volume={41},
 632   number={1},
 633   pages={69--85},
 634   year={2001}
 635 }
 636
 637 @article{ fredman:sst,
 638   title={{Storing a Sparse Table with $\O(1)$ Worst Case Access Time}},
 639   author={Fredman, M.L. and Koml{\'o}s, J. and Szemer{\'e}di, E.},
 640   journal={Journal of the ACM (JACM)},
 641   volume={31},
 642   number={3},
 643   pages={538--544},
 644   year={1984},
 645   publisher={ACM Press New York, NY, USA}
 646 }
 647
 648 @book{ motwani:randalg,
 649   title={{Randomized Algorithms}},
 650   author={Motwani, R. and Raghavan, P.},
 651   year={1995},
 652   publisher={Cambridge University Press}
 653 }
 654
 655 @article{ fw:fusion,
 656   title={{Surpassing the information theoretic bound with fusion trees}},
 657   author={Fredman, M.L. and Willard, D.E.},
 658   journal={Journal of Computer and System Sciences},
 659   volume={47},
 660   number={3},
 661   pages={424--436},
 662   year={1993},
 663   publisher={Academic Press, Inc. Orlando, FL, USA}
 664 }
 665
 666 @article{ han:detsort,
 667   title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}},
 668   author={Han, Y.},
 669   journal={Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing},
 670   pages={602--608},
 671   year={2002},
 672   publisher={ACM Press New York, NY, USA}
 673 }
 674
 675 @article{ hanthor:randsort,
 676   title={{Integer Sorting in $\O(n\sqrt{\log\log n})$ Expected Time and Linear Space}},
 677   author={Han, Y. and Thorup, M.},
 678   journal={Proceedings of the 43rd Symposium on Foundations of Computer Science},
 679   pages={135--144},
 680   year={2002},
 681   publisher={IEEE Computer Society Washington, DC, USA}
 682 }
 683
 684 @article{ ito:newrap,
 685   title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}},
 686   author={Ito, M. and Takagi, N. and Yajima, S.},
 687   journal={Proc. 12th IEEE Symp. Computer Arithmetic},
 688   pages={2--9},
 689   year={1995}
 690 }
 691
 692 @article{ brodnik:lsb,
 693   title={{Computation of the least significant set bit}},
 694   author={Brodnik, A.},
 695   journal={Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia},
 696   year={1993}
 697 }
 698
 699 @article{ turan:succinct,
 700   title={{Succinct representation of graphs.}},
 701   author={Tur\'an, G.},
 702   journal={Discrete Applied Mathematics},
 703   volume={8},
 704   number={3},
 705   pages={289--294},
 706   year={1984}
 707 }
 708
 709 @book{ jones:haskell,
 710   title={{Haskell 98 Language and Libraries: The Revised Report}},
 711   author={Jones, P. and Simon, L.},
 712   year={2003},
 713   publisher={Cambridge University Press}
 714 }
 715
 716 @article{ mader:dens,
 717   title={{Homomorphieeigenschaften und mittlere Kantendichte von Graphen}},
 718   author={Mader, W.},
 719   journal={Mathematische Annalen},
 720   volume={174},
 721   number={4},
 722   pages={265--268},
 723   year={1967},
 724   publisher={Springer},
 725   note={In German}
 726 }
 727
 728 @inproceedings{ gustedt:parallel,
 729     author = "Jens Gustedt",
 730     title = "Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel",
 731     booktitle = "Symposium on Theoretical Aspects of Computer Science",
 732     pages = "421-431",
 733     year = "1998",
 734     url = "citeseer.ist.psu.edu/223918.html"
 735 }
 736
 737 @article{ myrvold:rank,
 738   title={{Ranking and unranking permutations in linear time}},
 739   author={Myrvold, W.J. and Ruskey, F.},
 740   journal={Information Processing Letters},
 741   volume={79},
 742   number={6},
 743   pages={281--284},
 744   year={2001}
 745 }
 746
 747 @inproceedings{ critani:rau,
 748   title={{Ranking and unranking permutations with applications}},
 749   author={Critani, F. and Dall'Aglio, M. and Di Biase, G.},
 750   booktitle={Innovation in Mathematics: Proceedings of Second International Mathematica Symposium},
 751   pages = "99-106",
 752   year = "1997"
 753 }
 754
 755 @article{ ruskey:ham,
 756   title={{The Hamiltonicity of directed-Cayley graphs (or: A tale of backtracking)}},
 757   author={Ruskey, F. and Jiang, M. and Weston, A.},
 758   journal={Discrete Appl. Math},
 759   volume={57},
 760   pages={75--83},
 761   year={1995}
 762 }
 763
 764 @article{ ruskey:hce,
 765   title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn}},
 766   author={Ruskey, F. and Savage, C.D.},
 767   journal={SIAM Journal on Discrete Mathematics},
 768   volume={6},
 769   number={1},
 770   pages={152--166},
 771   year={1993}
 772 }
 773
 774 @article{ liehe:raulow,
 775   title={{Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis}},
 776   author={Liebehenschel, J.},
 777   journal={Journal of Automata, Languages and Combinatorics},
 778   volume={2},
 779   number={4},
 780   pages={227--268},
 781   year={1997}
 782 }
 783
 784 @book{ reingold:catp,
 785   title={{Combinatorial Algorithms: Theory and Practice}},
 786   author={Reingold, E.M.},
 787   year={1977},
 788   publisher={Prentice Hall College Div}
 789 }
 790
 791 @inproceedings{ dietz:oal,
 792  author = {Paul F. Dietz},
 793  title = {Optimal Algorithms for List Indexing and Subset Rank},
 794  booktitle = {WADS '89: Proceedings of the Workshop on Algorithms and Data Structures},
 795  year = {1989},
 796  isbn = {3-540-51542-9},
 797  pages = {39--46},
 798  publisher = {Springer-Verlag},
 799  address = {London, UK},
 800 }
 801
 802 @book { ss:fifteen,
 803   title={{The 15 Puzzle Book}},
 804   author={Slocum, J. and Sonneveld D.},
 805   year={2006},
 806   publisher={The Slocum Puzzle Foundation, Beverly Hills, CA, USA}
 807 }
 808
 809 @article{ rs:wagner,
 810   title={{Graph minors: XX. Wagner's Conjecture}},
 811   author={Robertson, N. and Seymour, P. D.},
 812   journal={Journal of Combinatorial Theory Series B},
 813   volume={92},
 814   number={2},
 815   pages={325--357},
 816   year={2004},
 817   publisher={Academic Press, Inc. Orlando, FL, USA}
 818 }
 819
 820 @book{ matnes:idm,
 821   title={{Invitation to Discrete Mathematics}},
 822   author={Matou{\v{s}}ek, J. and Ne{\v{s}}et{\v{r}}il, J.},
 823   year={1998},
 824   publisher={Oxford University Press}
 825 }
 826
 827 @article{ stanley:econe,
 828   title={{Enumerative combinatorics. Vol. 1}},
 829   author={Stanley, R.P.},
 830   journal={Cambridge Studies in Advanced Mathematics},
 831   volume={49},
 832   year={1997}
 833 }
 834
 835 @article{ kaplansky:rooks,
 836   title={{The problem of the rooks and its applications}},
 837   author={Kaplansky, I. and Riordan, J.},
 838   journal={Duke Math. J},
 839   volume={13},
 840   number={2},
 841   pages={259--268},
 842   year={1946}
 843 }
 844
 845 @article{ dinic:flow,
 846   author = {E. A. Dinic},
 847   title = {Algorithm for solution of a problem of maximum flow in networks with power estimation},
 848   journal = {Soviet Math. Dokl.},
 849   volume = {11},
 850   year = {1970},
 851   pages = {1277--1280}
 852 }
 853
 854 @article{ even:dinic,
 855   author = {Shimon Even and Robert Endre Tarjan},
 856   title = {Network Flow and Testing Graph Connectivity},
 857   publisher = {SIAM},
 858   year = {1975},
 859   journal = {SIAM Journal on Computing},
 860   volume = {4},
 861   number = {4},
 862   pages = {507--518},
 863   url = {http://link.aip.org/link/?SMJ/4/507/1},
 864   doi = {10.1137/0204043}
 865 }
 866
 867 @article{ valiant:permanent,
 868   title={{The complexity of computing the permanent}},
 869   author={Valiant, L. G.},
 870   journal={Theoretical Computer Science},
 871   volume={8},
 872   number={2},
 873   pages={189--201},
 874   year={1979}
 875 }
 876
 877 @article{ jerrum:permanent,
 878   title={{A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries}},
 879   author={Jerrum, M. and Sinclair, A. and Vigoda, E.},
 880   journal={Journal of the ACM},
 881   volume={51},
 882   number={4},
 883   pages={671--697},
 884   year={2004}
 885 }
 886
 887 @article{ kasteleyn:crystals,
 888   title={{Graph theory and crystal physics}},
 889   author={Kasteleyn, P. W.},
 890   journal={Graph Theory and Theoretical Physics},
 891   publisher={Academic Press, London},
 892   pages={43--110},
 893   year={1967}
 894 }
 895
 896 @article{ yuster:matching,
 897   title={{Maximum matching in graphs with an excluded minor}},
 898   author={Yuster, R. and Zwick, U.},
 899   journal={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
 900   pages={108--117},
 901   year={2007},
 902   publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
 903 }
 904
 905 @article{ mucha:matching,
 906   title={{Maximum Matchings in Planar Graphs via Gaussian Elimination}},
 907   author={Mucha, M. and Sankowski, P.},
 908   journal={Algorithmica},
 909   volume={45},
 910   number={1},
 911   pages={3--20},
 912   year={2006},
 913   publisher={Springer}
 914 }
 915
 916 @article {lovasz:minors,
 917   title={{Graph Minor Theory}},
 918   author={Lov\'asz, L.},
 919   journal={Bulletin of the American Mathematical Society},
 920   volume={43},
 921   number={1},
 922   pages={75--86},
 923   year={2005}
 924 }
 925
 926 @article{ andersson:fusion,
 927   title={{Fusion trees can be implemented with AC0 instructions only}},
 928   author={Andersson, A. and Miltersen, P.B. and Thorup, M.},
 929   journal={Theoretical Computer Science},
 930   volume={215},
 931   number={1-2},
 932   pages={337--344},
 933   year={1999},
 934   publisher={Elsevier}
 935 }
 936
 937 @article{ thorup:rampq,
 938   title={{On RAM priority queues}},
 939   author={THORUP, M.},
 940   journal={SIAM journal on computing(Print)},
 941   volume={30},
 942   number={1},
 943   pages={86--109},
 944   year={2001},
 945   publisher={Society for Industrial and Applied Mathematics}
 946 }
 947
 948 @article{ thorup:pqsssp,
 949   title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
 950   author={Thorup, M.},
 951   journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
 952   pages={149--158},
 953   year={2003},
 954   publisher={ACM Press New York, NY, USA}
 955 }
 956
 957 @article{ chazelle:mstapprox,
 958   title={{Approximating the Minimum Spanning Tree Weight in Sublinear Time}},
 959   author={Chazelle, B. and Rubinfeld, R. and Trevisan, L.},
 960   journal={SIAM Journal on Computing},
 961   volume={34},
 962   pages={1370},
 963   year={2005},
 964   publisher={SIAM}
 965 }
 966
 967 @inproceedings{ czumaj:metric,
 968  author = {Artur Czumaj and Christian Sohler},
 969  title = {Estimating the weight of metric minimum spanning trees in sublinear-time},
 970  booktitle = {STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},
 971  year = {2004},
 972  isbn = {1-58113-852-0},
 973  pages = {175--183},
 974  location = {Chicago, IL, USA},
 975  doi = {http://doi.acm.org/10.1145/1007352.1007386},
 976  publisher = {ACM},
 977  address = {New York, NY, USA},
 978 }
 979
 980 @inproceedings{ czumaj:euclidean,
 981  author = {Artur Czumaj and Funda Erg\"{u}n and Lance Fortnow and Avner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler},
 982  title = {Sublinear-time approximation of Euclidean minimum spanning tree},
 983  booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
 984  year = {2003},
 985  isbn = {0-89871-538-5},
 986  pages = {813--822},
 987  location = {Baltimore, Maryland},
 988  publisher = {Society for Industrial and Applied Mathematics},
 989  address = {Philadelphia, PA, USA},
 990 }
 991
 992 @book{ ieee:binfp,
 993   author = {IEEE},
 994   title = {IEEE Standard 754-1985 for Binary Floating-point Arithmetic},
 995   year = {1985},
 996   publisher = {IEEE}
 997 }
 998
 999 @article{ dgoldberg:fp,
1000   title={{What every computer scientist should know about floating-point arithmetic}},
1001   author={Goldberg, D.},
1002   journal={ACM Computing Surveys (CSUR)},
1003   volume={23},
1004   number={1},
1005   pages={5--48},
1006   year={1991},
1007   publisher={ACM Press New York, NY, USA}
1008 }
1009
1010 @article{ thorup:floatint,
1011   title={{Floats, Integers, and Single Source Shortest Paths}},
1012   author={Thorup, M.},
1013   journal={Journal of Algorithms},
1014   volume={35},
1015   number={2},
1016   pages={189--201},
1017   year={2000},
1018   publisher={Academic Press}
1019 }
1020
1021 @article{ shamos:closest,
1022   title={{Closest-point problems}},
1023   author={Shamos, M. I. and Hoey, D.},
1024   journal={Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science},
1025   pages={151--162},
1026   year={1975}
1027 }
1028
1029 @article{ fortune:voronoi,
1030   title={{A sweepline algorithm for Voronoi diagrams}},
1031   author={Fortune, S.},
1032   journal={Algorithmica},
1033   volume={2},
1034   number={1},
1035   pages={153--174},
1036   year={1987},
1037   publisher={Springer}
1038 }
1039
1040 @article{ zhou:nodel,
1041   title={{Efficient minimum spanning tree construction without Delaunay triangulation}},
1042   author={Zhou, H. and Shenoy, N. and Nicholls, W.},
1043   journal={Information Processing Letters},
1044   volume={81},
1045   number={5},
1046   pages={271--276},
1047   year={2002},
1048   publisher={Elsevier}
1049 }
1050
1051 @techreport{ eppstein:spanning,
1052   title={{Spanning Trees and Spanners}},
1053   author={Eppstein, D.},
1054   year={1996},
1055   institution={Information and Computer Science, University of California, Irvine}
1056 }
1057
1058 @article{ garey:steiner,
1059   title={{The Complexity of Computing Steiner Minimal Trees}},
1060   author={Garey, M.R. and Graham, R.L. and Johnson, D.S.},
1061   journal={SIAM Journal on Applied Mathematics},
1062   volume={32},
1063   number={4},
1064   pages={835--859},
1065   year={1977},
1066 }
1067
1068 @article{ garey:rectisteiner,
1069   title={{The Rectilinear Steiner Tree Problem is NP-Complete}},
1070   author={Garey, M.R. and Johnson, D.S.},
1071   journal={SIAM Journal on Applied Mathematics},
1072   volume={32},
1073   number={4},
1074   pages={826--834},
1075   year={1977},
1076 }
1077
1078 @article{ proemel:steiner,
1079   title={{A new approximation algorithm for the Steiner tree problem with performance ratio $5/3$}},
1080   author={Promel, H.J. and Steger, A.},
1081   journal={Journal of Algorithms},
1082   volume={36},
1083   pages={89--101},
1084   year={2000}
1085 }
1086
1087 @article{ arora:tspapx,
1088   title={{Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems}},
1089   author={Arora, S.},
1090   journal={Journal of the ACM (JACM)},
1091   volume={45},
1092   number={5},
1093   pages={753--782},
1094   year={1998},
1095   publisher={ACM Press New York, NY, USA}
1096 }
1097
1098 @article{ harel:nca,
1099   title={{Fast algorithms for finding nearest common ancestors}},
1100   author={Harel, D. and Tarjan, R.E.},
1101   journal={SIAM Journal on Computing},
1102   volume={13},
1103   number={2},
1104   pages={338--355},
1105   year={1984},
1106   publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
1107 }
1108
1109 @article{ gomoryhu,
1110    author = "R. E. Gomory and T. C. Hu",
1111    title = "Multi-Terminal Network Flows",
1112    journal = "{Journal of SIAM}",
1113    volume = {9},
1114    number = {4},
1115    year = {1961},
1116    pages = {551--570}
1117 }
1118
1119 @inproceedings{ bhalgat:ght,
1120  author = {Ramesh Hariharan and Telikepalli Kavitha and Debmalya Panigrahi and Anand Bhalgat},
1121  title = {{An $\widehat\O(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs}},
1122  booktitle = {STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing},
1123  year = {2007},
1124  isbn = {978-1-59593-631-8},
1125  pages = {605--614},
1126  location = {San Diego, California, USA},
1127  doi = {http://doi.acm.org/10.1145/1250790.1250879},
1128  publisher = {ACM},
1129  address = {New York, NY, USA},
1130 }
1131
1132 @article{ sleator:trees,
1133   title={{A data structure for dynamic trees}},
1134   author={Sleator, D.D. and Tarjan, R.E.},
1135   journal={Journal of Computer and System Sciences},
1136   volume={26},
1137   number={3},
1138   pages={362--391},
1139   year={1983},
1140   publisher={Academic Press, Inc. Orlando, FL, USA}
1141 }
1142
1143 @article{ chernoff,
1144   title={{A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations}},
1145   author={Chernoff, H.},
1146   journal={The Annals of Mathematical Statistics},
1147   volume={23},
1148   number={4},
1149   pages={493--507},
1150   year={1952},
1151   publisher={JSTOR}
1152 }
1153
1154 @article{ pettie:parallel,
1155  author       = {Seth Pettie and Vijaya Ramachandran},
1156  title        = {A randomized time-work optimal parallel algorithm for
1157                  finding a minimum spanning forest},
1158  journal      = {SIAM J. Comput.},
1159  volume       = {31},
1160  number       = {6},
1161  year         = {2002},
1162  pages        = {1879--1895},
1163 }
1164
1165 @article{ chazelle:softheap,
1166  author = {Bernard Chazelle},
1167  title = {The soft heap: an approximate priority queue with optimal error rate},
1168  journal = {J. ACM},
1169  volume = {47},
1170  number = {6},
1171  year = {2000},
1172  issn = {0004-5411},
1173  pages = {1012--1027},
1174  doi = {http://doi.acm.org/10.1145/355541.355554},
1175  publisher = {ACM},
1176  address = {New York, NY, USA},
1177 }
1178
1179 @article{ propp:randommst,
1180  author = {James Gary Propp and David Bruce Wilson},
1181  title = {How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph},
1182  journal = {J. Algorithms},
1183  volume = {27},
1184  number = {2},
1185  year = {1998},
1186  issn = {0196-6774},
1187  pages = {170--217},
1188  doi = {http://dx.doi.org/10.1006/jagm.1997.0917},
1189  publisher = {Academic Press, Inc.},
1190  address = {Duluth, MN, USA},
1191 }
1192
1193 @article{ vuillemin:binheap,
1194   title={{A Data Structure for Manipulating Priority Queues}},
1195   author={Vuillemin, Jean},
1196   journal={Communications of the ACM},
1197   volume = 21,
1198   number = 4,
1199   pages={309--315},
1200   year={1978}
1201 }
1202
1203 @article{ hoare:qsort,
1204   title={{Quicksort}},
1205   author={Hoare, Charles Anthony Richard},
1206   journal={The Computer Journal},
1207   volume={5},
1208   number={1},
1209   pages={10--16},
1210   year={1962},
1211   publisher={British Computer Society}
1212 }
1213
1214 @article{ blum:selection,
1215   title={{Time bounds for selection}},
1216   author={Blum, M. and Floyd, R.W. and Pratt, V. and Rivest, R.L. and Tarjan, R.E.},
1217   journal={Journal of Computer and System Sciences},
1218   volume={7},
1219   number={4},
1220   pages={448--461},
1221   year={1973}
1222 }
1223
1224 @article{ hoare:qselect,
1225  author = {Hoare, Charles Anthony Richard},
1226  title = {Algorithm 65: find},
1227  journal = {Communications of the ACM},
1228  volume = {4},
1229  number = {7},
1230  year = {1961},
1231  issn = {0001-0782},
1232  pages = {321--322},
1233  doi = {http://doi.acm.org/10.1145/366622.366647},
1234  publisher = {ACM},
1235  address = {New York, NY, USA},
1236 }
1237
1238 @article{ dinitz:treeiso,
1239   title={{On an algorithm of Zemlyachenko for subtree isomorphism}},
1240   author={Dinitz, Y. and Itai, A. and Rodeh, M.},
1241   journal={Information Processing Letters},
1242   volume={70},
1243   number={3},
1244   pages={141--146},
1245   year={1999},
1246   publisher={Elsevier}
1247 }
1248
1249 @inproceedings{ zemlay:treeiso,
1250   title={{Determining tree isomorphism}},
1251   author={Zemlayachenko, V. N.},
1252   booktitle={{Voprosy Kibernetiki, Proceedings of the Seminar on Combinatorial Mathematics}},
1253   location={Moscow 1971},
1254   publisher={{Scientific Council of the Complex Problem ``Kibernetika'', Akad. Nauk SSSR}},
1255   year={1973},
1256   pages={54--60},
1257   note={In Russian},
1258 }
1259
1260 @article{ alstrup:marked,
1261   title={{Marked ancestor problems}},
1262   author={Alstrup, S. and Husfeldt, T. and Rauhe, T.},
1263   journal={Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on},
1264   pages={534--543},
1265   year={1998}
1266 }
1267
1268 @article{ arvind:isomorph,
1269   title={{Graph isomorphism is in SPP}},
1270   author={Arvind, V. and Kurur, P. P.},
1271   journal={Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on},
1272   pages={743--750},
1273   year={2002}
1274 }
1275
1276 @article{ ackermann:function,
1277   title={{Zum Hilbertschen Aufbau der reellen Zahlen}},
1278   author={Ackermann, W.},
1279   journal={Mathematische Annalen},
1280   volume={99},
1281   number={1},
1282   pages={118--133},
1283   year={1928},
1284   publisher={Springer},
1285   notes={In German}
1286 }
1287
1288 @article{ klazar:gdss,
1289   title={{Generalized Davenport--Schinzel Sequences: Results, problems, and applications}},
1290   author={Klazar, M.},
1291   journal={INTEGERS: The Electronic Journal of Combinatorial Number Theory},
1292   volume={2},
1293   number={A11},
1294   pages={2},
1295   year={2002}
1296 }
1297
1298 @inproceedings{ fredman:cellprobe,
1299   author = {M. Fredman and M. Saks},
1300   title = {The cell probe complexity of dynamic data structures},
1301   booktitle = {STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing},
1302   year = {1989},
1303   isbn = {0-89791-307-8},
1304   pages = {345--354},
1305   location = {Seattle, Washington, United States},
1306   doi = {http://doi.acm.org/10.1145/73007.73040},
1307   publisher = {ACM},
1308   address = {New York, NY, USA},
1309 }
1310
1311 @article{ henzinger:randdyn,
1312   title={{Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation}},
1313   author={Henzinger, M.R. and King, V.},
1314   journal={Journal of the ACM},
1315   volume={46},
1316   number={4},
1317   pages={502--516},
1318   year={1999}
1319 }
1320
1321 @article{ holm:polylog,
1322   title={{Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity}},
1323   author={Holm, J. and de Lichtenberg, K. and Thorup, M.},
1324   journal={Journal of the ACM (JACM)},
1325   volume={48},
1326   number={4},
1327   pages={723--760},
1328   year={2001},
1329   publisher={ACM Press New York, NY, USA}
1330 }
1331
1332 @article{ frederickson:dynamic,
1333   title={{Data structures for on-line updating of minimum spanning trees, with applications}},
1334   author={Frederickson, G. N.},
1335   journal={SIAM Journal of Computing},
1336   volume={14},
1337   pages={781--798},
1338   year={1985}
1339 }
1340
1341 @article{ eppstein:sparsify,
1342   title={{Sparsification --- a technique for speeding up dynamic graph algorithms}},
1343   author={Eppstein, D. and Galil, Z. and Italiano, G.F. and Nissenzweig, A.},
1344   journal={Journal of the ACM},
1345   volume={44},
1346   number={5},
1347   pages={669--696},
1348   year={1997},
1349   publisher={ACM Press New York, NY, USA}
1350 }
1351
1352 @article{ henzinger:mst,
1353   title={{Maintaining minimum spanning trees in dynamic graphs}},
1354   author={Henzinger, M.R. and King, V.},
1355   journal={Proceedings of the 24th International Colloquium on Automata, Languages and Programming},
1356   pages={594--604},
1357   year={1997},
1358   publisher={Springer}
1359 }
1360
1361 @mastersthesis { mares:dga,
1362   title={{Dynamick\'e grafov\'e algoritmy}},
1363   author={Martin Mare\v{s}},
1364   school={Charles University in Prague, Faculty of Math and Physics},
1365   year={2000}
1366 }
1367
1368 @techreport{ henzinger:twoec,
1369   title = {Fully dynamic 2-edge-connectivity algorithm in polylogarithmic time per operation},
1370   author = {Monika Rauch Henzinger and Valerie King},
1371   type = {Technical note},
1372   institution = {Digital Equipment Corp., Systems Research Ctr.},
1373   address = {130 Lytton Rd., Palo Alto, CA, 94301, USA},
1374   number = {1997-004},
1375   month = {12 Jun},
1376   year = {1997},
1377   url = {http://gatekeeper.dec.com/pub/DEC/SRC/technical-notes/abstracts/src-tn-1997-004.html}
1378 }
1379
1380 @book{ overmars:ds,
1381   author = {Mark H. Overmars},
1382   title = {Design of Dynamic Data Structures},
1383   year = {1987},
1384   isbn = {038712330X},
1385   publisher = {Springer-Verlag New York, Inc.},
1386   address = {Secaucus, NJ, USA},
1387   series={{Lecture Notes in Computer Science}},
1388   volume={156}
1389 }
1390
1391 @article{ eppstein:ksmallest,
1392   title={{Finding the $k$~Smallest Spanning Trees}},
1393   author={Eppstein, D.},
1394   journal={BIT},
1395   volume={32},
1396   number={2},
1397   pages={237--248},
1398   year={1992},
1399   publisher={Springer}
1400 }
1401
1402 @article{ katoh:ksmallest,
1403   title={{An Algorithm for Finding\$ K\$ Minimum Spanning Trees}},
1404   author={Katoh, N. and Ibaraki, T. and Mine, H.},
1405   journal={SIAM Journal on Computing},
1406   volume={10},
1407   pages={247},
1408   year={1981},
1409   publisher={SIAM}
1410 }
1411
1412 @inproceedings{ thorup:nearopt,
1413  author = {Mikkel Thorup},
1414  title = {Near-optimal fully-dynamic graph connectivity},
1415  booktitle = {STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing},
1416  year = {2000},
1417  isbn = {1-58113-184-4},
1418  pages = {343--350},
1419  location = {Portland, Oregon, United States},
1420  doi = {http://doi.acm.org/10.1145/335305.335345},
1421  publisher = {ACM},
1422  address = {New York, NY, USA},
1423 }
1424
1425 @article{ henzinger:lowerbounds,
1426   title={{Lower Bounds for Fully Dynamic Connectivity Problems in Graphs}},
1427   author={Henzinger, M. R. and Fredman, M. L.},
1428   journal={Algorithmica},
1429   volume={22},
1430   number={3},
1431   pages={351--362},
1432   year={1998},
1433   publisher={Springer}
1434 }
1435
1436 @article{ thorup:usssp,
1437   title={{Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time}},
1438   author={Thorup, Mikkel},
1439   journal={Journal of the ACM},
1440   volume={46},
1441   number={3},
1442   pages={362--394},
1443   year={1999}
1444 }
1445
1446 @article{ thorup:sssp,
1447   author = {Mikkel Thorup},
1448   title = {Integer priority queues with decrease key in constant time and the single source shortest paths problem},
1449   journal = {Journal of Computer and System Sciences},
1450   volume = {69},
1451   number = {3},
1452   year = {2004},
1453   issn = {0022-0000},
1454   pages = {330--353},
1455   doi = {http://dx.doi.org/10.1016/j.jcss.2004.04.003},
1456   publisher = {Academic Press, Inc.},
1457   address = {Orlando, FL, USA},
1458 }
1459
1460 @inproceedings{ hagerup:sssp,
1461   author = {Torben Hagerup},
1462   title = {Improved Shortest Paths on the Word RAM},
1463   booktitle = {ICALP '00: Proceedings of the 27th International Colloquium on Automata, Languages and Programming},
1464   year = {2000},
1465   isbn = {3-540-67715-1},
1466   pages = {61--72},
1467   publisher = {Springer-Verlag},
1468   address = {London, UK},
1469 }