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