biblio.bib

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