biblio.bib

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