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