biblio.bib

   1 @inproceedings{ bender00lca,
   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 @inproceedings{ thorup:aczero,
  52  author = {Mikkel Thorup},
  53  title = {On AC0 implementations of fusion trees and atomic heaps},
  54  booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
  55  year = {2003},
  56  isbn = {0-89871-538-5},
  57  pages = {699--707},
  58  location = {Baltimore, Maryland},
  59  publisher = {Society for Industrial and Applied Mathematics},
  60  address = {Philadelphia, PA, USA},
  61  }
  62
  63 @article{ benamram:pm,
  64     author = "Ben-Amram, Amir M.",
  65     title = "What is a ``Pointer Machine''?",
  66     journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
  67     volume = "26",
  68     year = "1995",
  69     url = "citeseer.ist.psu.edu/ben-amram95what.html" }
  70
  71 @article{ matsui:planar,
  72     author = "Tomomi Matsui",
  73     title = "{The Minimum Spanning tree Problem on a Planar Graph}",
  74     journal = "Discrete Applied Mathematics",
  75     volume = "58",
  76     year = "1995",
  77     pages = "91--94",
  78     url = "citeseer.nj.nec.com/2319.html"
  79 }
  80
  81 @article{ chazelle:ackermann,
  82     author = "Bernard Chazelle",
  83     title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
  84     journal = jacm,
  85     volume = "47",
  86     pages = "1028--1047",
  87     year = "2000"
  88 }
  89
  90 @article{ nesetril:history,
  91     author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
  92     title = "{Some remarks on the history of MST-problem}",
  93     journal = "Archivum Mathematicum",
  94     volume = "33",
  95     pages = "15--22",
  96     year = "1997"
  97 }
  98
  99 @article{ nesetril:boruvka,
 100     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
 101     title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
 102     journal = "Discrete Mathematics",
 103     volume = "233(1--3)",
 104     pages = "3--36",
 105     year = "2001"
 106 }
 107
 108 @incollection { nesetril:minors,
 109     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
 110     title = "{Colorings and Homomorphisms of Minor Closed Classes}",
 111     booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
 112     editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
 113     year = "2003",
 114     pages = "651--664",
 115     publisher = "Springer Verlag"
 116 }
 117
 118 @article { boruvka:ojistem,
 119     author = "Otakar Bor{\accent23u}vka",
 120     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
 121     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
 122     volume = "III",
 123     year = "1926",
 124     pages = "37--58",
 125     note = "Czech with German summary"
 126 }
 127
 128 @article { boruvka:networks,
 129     author = "Otakar Bor{\accent23u}vka",
 130     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)}",
 131     journal = "Elektronick\'y obzor",
 132     volume = "15",
 133     year = "1926",
 134     pages = "153--154",
 135     note = "Czech"
 136 }
 137
 138 @article { jarnik:ojistem,
 139     author = "Vojt\v{e}ch Jarn\'\i{}k",
 140     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
 141     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
 142     volume = "VI",
 143     year = "1930",
 144     pages = "57--63",
 145     note = "Czech"
 146 }
 147
 148 @book { tarjan:dsna,
 149     author = "Robert E. Tarjan",
 150     title = "{Data structures and network algorithms}",
 151     series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}",
 152     volume = 44,
 153     year = "1983",
 154     publisher = "SIAM"
 155 }
 156
 157 @article { gh:history,
 158     author = "R. L. Graham and P. Hell",
 159     title = "{On the history of the minimum spanning tree problem}",
 160     journal = "{Annals of the History of Computing}",
 161     volume = "7",
 162     year = "1985",
 163     pages = "43--57"
 164 }
 165
 166 @techreport { pettie:ackermann,
 167     author = "Seth Pettie",
 168     title = "{Finding minimum spanning trees in $O(m\alpha(m,n))$ time}",
 169     institution = "Univ. of Texas at Austin",
 170     year = "1999",
 171     number = "TR99-23",
 172     type = "Tech Report"
 173 }
 174
 175 @inproceedings { pettie:optimal,
 176    author = "Seth Pettie and Vijaya Ramachandran",
 177    title = "{An Optimal Minimum Spanning Tree Algorithm}",
 178    booktitle = "{Proceedings of ICALP'2000}",
 179    year = "2000",
 180    publisher = "Springer Verlag",
 181    pages = "49--60"
 182 }
 183
 184 @article { pettie:alpha,
 185   title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}},
 186   author={Pettie, S.},
 187   year={1999},
 188   publisher={University of Texas at Austin Austin, TX, USA}
 189 }
 190
 191 @article { karger:randomized,
 192    author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
 193    title = "{Linear expected-time algorithms for connectivity problems}",
 194    journal = jacm,
 195    volume = "42",
 196    pages = "321--328",
 197    year = "1995"
 198 }
 199
 200 @article { frederickson:online,
 201    author = "Greg N. Frederickson",
 202    title = "{Data structures for on-line updating of minimum spanning trees}",
 203    journal = "{SIAM Journal on Computing}",
 204    volume = "14",
 205    pages = "781--798",
 206    year = "1985"
 207 }
 208
 209 @article { mm:mst,
 210    author = "Martin Mare\v{s}",
 211    title = "{Two linear time algorithms for MST on minor closed graph classes}",
 212    journal = "{Archivum Mathematicum}",
 213    volume = "40",
 214    pages = "315--320",
 215    year = "2004"
 216 }
 217
 218 @article{ ft:fibonacci,
 219  author = {Michael L. Fredman and Robert Endre Tarjan},
 220  title = {Fibonacci heaps and their uses in improved network optimization algorithms},
 221  journal = {J. ACM},
 222  volume = {34},
 223  number = {3},
 224  year = {1987},
 225  issn = {0004-5411},
 226  pages = {596--615},
 227  doi = {http://doi.acm.org/10.1145/28869.28874},
 228  publisher = {ACM Press},
 229  address = {New York, NY, USA},
 230  }
 231
 232 @article{ komlos:verify,
 233   author    = {J{\'a}nos Koml{\'o}s},
 234   title     = {Linear verification for spanning trees.},
 235   journal   = {Combinatorica},
 236   volume    = {5},
 237   number    = {1},
 238   year      = {1985},
 239   pages     = {57--65},
 240   bibsource = {DBLP, http://dblp.uni-trier.de}
 241 }
 242
 243 @inproceedings{ king:verify,
 244     author = "Valerie King",
 245     title = "A Simpler Minimum Spanning Tree Verification Algorithm",
 246     booktitle = "Workshop on Algorithms and Data Structures",
 247     pages = "440--448",
 248     year = "1995",
 249     url = "citeseer.ist.psu.edu/king95simpler.html" }
 250
 251 @article{ king:verifytwo,
 252   title={{A Simpler Minimum Spanning Tree Verification Algorithm}},
 253   author={King, Valerie},
 254   journal={Algorithmica},
 255   volume={18},
 256   pages={263--270},
 257   year={1997}
 258 }
 259
 260 @book { schrijver,
 261     author = "Alexander Schrijver",
 262     title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
 263     series = "Algorithms and Combinatorics",
 264     volume = 24,
 265     year = 2003,
 266     publisher = "Springer Verlag"
 267 }
 268
 269 @inproceedings{ thorup:ac0,
 270  author = {Mikkel Thorup},
 271  title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
 272  booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
 273  year = {2003},
 274  isbn = {0-89871-538-5},
 275  pages = {699--707},
 276  location = {Baltimore, Maryland},
 277  publisher = {Society for Industrial and Applied Mathematics},
 278  address = {Philadelphia, PA, USA},
 279 }
 280
 281 @article{ kruskal:mst,
 282   title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
 283   author={Kruskal Jr, J.B.},
 284   journal={Proceedings of the American Mathematical Society},
 285   volume={7},
 286   number={1},
 287   pages={48--50},
 288   year={1956},
 289   publisher={JSTOR}
 290 }
 291
 292 @book{ diestel:gt,
 293   title={{Graph Theory}},
 294   author={Diestel, R.},
 295   year={2005},
 296   publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K}
 297 }
 298
 299 @article{ thorup:pq,
 300   title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
 301   author={Thorup, M.},
 302   journal={Proceedings of the thirty-fifth ACM symposium on Theory of computing},
 303   pages={149--158},
 304   year={2003},
 305   publisher={ACM Press New York, NY, USA}
 306 }
 307
 308 @article{ graham:msthistory,
 309   title={{On the history of the minimum spanning tree problem}},
 310   author={Graham, R.L. and Hell, P.},
 311   journal={Annals of the History of Computing},
 312   volume={7},
 313   number={1},
 314   pages={43--57},
 315   year={1985}
 316 }
 317
 318 @article{ cayley:trees,
 319   title={{A theorem on trees}},
 320   author={Cayley, Arthur},
 321   journal={Quart. J. Math},
 322   volume={23},
 323   year={1889},
 324   pages={376--378}
 325 }
 326
 327 @article{ dijkstra:mst,
 328   title={{A note on two problems in connexion with graphs}},
 329   author = "Dijkstra, E. W.",
 330   journal={Numerische Mathematik},
 331   volume={1},
 332   number={1},
 333   pages={269--271},
 334   year={1959},
 335   publisher={Springer}
 336 }
 337
 338 @article{ prim:mst,
 339   author = "Prim, R. C.",
 340   title = "Shortest connection networks and some generalizations",
 341   journal = "Bell System Technical Journal",
 342   volume = "36",
 343   year = "1957",
 344   pages={567--574},
 345 }
 346
 347 @article{ choquet:mst,
 348   title={{Etude de certains r{\'e}seaux de routes (in French)}},
 349   author={Choquet, Gustave},
 350   journal={Comptes-rendus de l'Académie des Sciences},
 351   volume={206},
 352   pages={310},
 353   year={1938}
 354 }
 355
 356 @incollection { sollin:mst,
 357   title={{Le trace de canalisation (in French)}},
 358   author={Sollin, M.},
 359   booktitle={Programming, Games, and Transportation Networks},
 360   editor={Berge, C. and Ghouilla-Houri, A.},
 361   publisher={Wiley, New York},
 362   year={1965}
 363 }
 364
 365 @article{ boyer:cutting,
 366   title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
 367   author={Boyer, J.M. and Myrvold, W.J.},
 368   journal={Journal of Graph Algorithms and Applications},
 369   volume={8},
 370   number={3},
 371   pages={241--273},
 372   year={2004}
 373 }
 374
 375 @inproceedings{ takaoka:twothree,
 376   title={{Theory of 2-3 Heaps}},
 377   author={Takaoka, T. and Christchurch, N. Z.},
 378   booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON'99},
 379   location={Tokyo, Japan},
 380   year={1999},
 381   pages={41--50},
 382   publisher={Springer},
 383   series={{Lecture Notes in Computer Science}},
 384   volume={1627}
 385 }
 386
 387 @inproceedings{ takaoka:trinomial,
 388   title={{Theory of Trinomial Heaps}},
 389   author={Takaoka, Tadao},
 390   booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
 391   location={Sydney, Australia},
 392   year={2000},
 393   pages={362--372},
 394   publisher={Springer},
 395   series={{Lecture Notes in Computer Science}},
 396   volume={1858}
 397 }
 398
 399 @book{ clrs,
 400   title={{Introduction to Algorithms}},
 401   author={Leiserson, C.E. and Rivest, R.L. and Cormen, T.H. and Stein, C.},
 402   year={2001},
 403   publisher={McGraw-Hill}
 404 }
 405
 406 @inproceedings{ pettie:onlineverify,
 407   author = "S. Pettie",
 408   title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
 409     tree verification problem",
 410   booktitle = "Proc. 43rd Annual Symp. on the Foundations of Computer Science, Vancouver, Canada",
 411   year = "2002",
 412   url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
 413 }
 414
 415 @article{ dixon:verify,
 416     author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
 417     title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
 418     journal = "SIAM J. Comput.",
 419     volume = "21",
 420     number = "6",
 421     pages = "1184-1192",
 422     year = "1992",
 423     url = "citeseer.ist.psu.edu/dixon92verification.html"
 424 }
 425
 426 inproceedings{ pettie:minirand,
 427  author = {Seth Pettie and Vijaya Ramachandran},
 428  title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
 429  booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms},
 430  year = {2002},
 431  isbn = {0-89871-513-X},
 432  pages = {713--722},
 433  location = {San Francisco, California},
 434  publisher = {Society for Industrial and Applied Mathematics},
 435  address = {Philadelphia, PA, USA}
 436 }
 437
 438 @article{ buchsbaum:verify,
 439   title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
 440   author={Buchsbaum, A.L. and Kaplan, H. and Rogers, A. and Westbrook, J.R.},
 441   journal={Proceedings of the thirtieth annual ACM symposium on Theory of computing},
 442   pages={279--288},
 443   year={1998},
 444   publisher={ACM Press New York, NY, USA}
 445 }
 446
 447 @article{ bacala:parametric,
 448   title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
 449   author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
 450   journal={Theoretical Computer Science},
 451   volume={181},
 452   number={1},
 453   pages={57--74},
 454   year={1997},
 455   publisher={Elsevier}
 456 }
 457
 458 @inproceedings{ katriel:cycle,
 459   author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
 460   title = "A practical minimum spanning tree algorithm using the cycle property",
 461   booktitle = "11th European Symposium on Algorithms(ESA)",
 462   number = "2832",
 463   series = "LNCS",
 464   pages = "679--690",
 465   publisher = "Springer",
 466   year = "2003",
 467   url = "citeseer.ist.psu.edu/katriel03practical.html"
 468 }
 469
 470 @article{ alstrup:nca,
 471   title={{Nearest common ancestors: a survey and a new distributed algorithm}},
 472   author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
 473   journal={Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures},
 474   pages={258--264},
 475   year={2002},
 476   publisher={ACM Press New York, NY, USA}
 477 }
 478
 479 @article{ gabow:mst,
 480   title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
 481   author={Gabow, H.N. and Galil, Z. and Spencer, T. and Tarjan, R.E.},
 482   journal={Combinatorica},
 483   volume={6},
 484   number={2},
 485   pages={109--122},
 486   year={1986},
 487   publisher={Springer}
 488 }
 489
 490 @Unpublished{ eisner:tutorial,
 491   author =       {Jason Eisner},
 492   title =        {State-of-the-Art Algorithms for Minimum Spanning
 493                   Trees: A Tutorial Discussion},
 494   note =         {Manuscript available online (78 pages), University of Pennsylvania},
 495   year =         1997,
 496   url =          {http://cs.jhu.edu/~jason/papers/#ms97},
 497 }
 498
 499 @article{ aho:lca,
 500   title={{On finding lowest common ancestors in trees.}},
 501   author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
 502   journal={SIAM Journal on Computing},
 503   volume={5},
 504   pages={115--132},
 505   year={1976}
 506 }
 507
 508 @book{ knuth:fundalg,
 509  author = {Donald E. Knuth},
 510  title = {The art of computer programming, volume 1 (3rd ed.): fundamental algorithms},
 511  year = {1997},
 512  isbn = {0-201-89683-4},
 513  publisher = {Addison Wesley Longman Publishing Co., Inc.},
 514  address = {Redwood City, CA, USA},
 515 }
 516
 517 @inproceedings{ hagerup:wordram,
 518  author = {Torben Hagerup},
 519  title = {{Sorting and Searching on the Word RAM}},
 520  booktitle = {STACS '98: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science},
 521  year = {1998},
 522  isbn = {3-540-64230-7},
 523  pages = {366--398},
 524  publisher = {Springer-Verlag},
 525  address = {London, UK},
 526 }
 527
 528 @inproceedings{ cook:ram,
 529  author = {Stephen A. Cook and Robert A. Reckhow},
 530  title = {Time-bounded random access machines},
 531  booktitle = {STOC '72: Proceedings of the fourth annual ACM symposium on Theory of computing},
 532  year = {1972},
 533  pages = {73--80},
 534  location = {Denver, Colorado, United States},
 535  doi = {http://doi.acm.org/10.1145/800152.804898},
 536  publisher = {ACM},
 537  address = {New York, NY, USA},
 538 }
 539
 540 @book{ okasaki:funcds,
 541   author = {Chris Okasaki},
 542   title = {Purely Functional Data Structures},
 543   year = {1999},
 544   publisher = {Cambridge University Press}
 545 }
 546
 547 @book { intel:pentium,
 548   author = {{Intel Corp.}},
 549   title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference},
 550   year = {2007},
 551   publisher = {Intel Corp.},
 552   xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
 553 }
 554
 555 @article{ hagerup:dd,
 556   title={{Deterministic Dictionaries}},
 557   author={Hagerup, T. and Miltersen, P.B. and Pagh, R.},
 558   journal={J. Algorithms},
 559   volume={41},
 560   number={1},
 561   pages={69--85},
 562   year={2001}
 563 }
 564
 565 @article{ fredman:sst,
 566   title={{Storing a Sparse Table with 0 (1) Worst Case Access Time}},
 567   author={Fredman, M.L. and Koml{\'o}s, J. and Szemer{\'e}di, E.},
 568   journal={Journal of the ACM (JACM)},
 569   volume={31},
 570   number={3},
 571   pages={538--544},
 572   year={1984},
 573   publisher={ACM Press New York, NY, USA}
 574 }
 575
 576 @book{ motwani:randalg,
 577   title={{Randomized Algorithms}},
 578   author={Motwani, R. and Raghavan, P.},
 579   year={1995},
 580   publisher={Cambridge University Press}
 581 }
 582
 583 @article{ fw:fusion,
 584   title={{Surpassing the information theoretic bound with fusion trees}},
 585   author={Fredman, M.L. and Willard, D.E.},
 586   journal={Journal of Computer and System Sciences},
 587   volume={47},
 588   number={3},
 589   pages={424--436},
 590   year={1993},
 591   publisher={Academic Press, Inc. Orlando, FL, USA}
 592 }
 593
 594 @article{ han:detsort,
 595   title={{Deterministic sorting in O (nlog log n) time and linear space}},
 596   author={Han, Y.},
 597   journal={Proceedings of the thiry-fourth annual ACM symposium on Theory of computing},
 598   pages={602--608},
 599   year={2002},
 600   publisher={ACM Press New York, NY, USA}
 601 }
 602
 603 @article{ hanthor:randsort,
 604   title={{Integer Sorting in 0 (n sqrt (log log n)) Expected Time and Linear Space}},
 605   author={Han, Y. and Thorup, M.},
 606   journal={Proceedings of the 43rd Symposium on Foundations of Computer Science},
 607   pages={135--144},
 608   year={2002},
 609   publisher={IEEE Computer Society Washington, DC, USA}
 610 }