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{ tarjan84setunion,
  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 { fw90trans,
  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{boas77,
  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{thorup03ac0,
  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{ benamram95what,
  64     author = "Ben-Amram",
  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 @unpublished { nesetril:minors,
 109     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
 110     title = "{Colorings and Homomorphism of Minor Closed Classes}",
 111     note = "To appear in {\it Pollack-Goodman Festschrift,} Springer Verlag, 2002."
 112 }
 113
 114 @article { boruvka:ojistem,
 115     author = "Otakar Bor{\accent23u}vka",
 116     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
 117     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
 118     volume = "III",
 119     year = "1926",
 120     pages = "37--58",
 121     note = "Czech with German summary"
 122 }
 123
 124 @book { tarjan:dsna,
 125     author = "Robert E. Tarjan",
 126     title = "{Data structures and network algorithms}",
 127     series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}",
 128     volume = 44,
 129     year = "1983",
 130     publisher = "SIAM"
 131 }
 132
 133 @article { gh:history,
 134     author = "R. L. Graham and P. Hell",
 135     title = "{On the history of the minimum spanning tree problem}",
 136     journal = "{Annals of the History of Computing}",
 137     volume = "7",
 138     year = "1985",
 139     pages = "43--57"
 140 }
 141
 142 @techreport { pettie:ackermann,
 143     author = "Seth Pettie",
 144     title = "{Finding minimum spanning trees in $O(m\alpha(m,n))$ time}",
 145     institution = "Univ. of Texas at Austin",
 146     year = "1999",
 147     number = "TR99-23",
 148     type = "Tech Report"
 149 }
 150
 151 @inproceedings { pettie:optimal,
 152    author = "Seth Pettie and Vijaya Ramachandran",
 153    title = "{An Optimal Minimum Spanning Tree Algorithm}",
 154    booktitle = "{Proceedings of ICALP'2000}",
 155    year = "2000",
 156    publisher = "Springer Verlag",
 157    pages = "49--60"
 158 }
 159
 160 @article { karger:randomized,
 161    author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
 162    title = "{Linear expected-time algorithms for connectivity problems}",
 163    journal = jacm,
 164    volume = "42",
 165    pages = "321--328",
 166    year = "1995"
 167 }
 168
 169 @article { frederickson:online,
 170    author = "Greg N. Frederickson",
 171    title = "{Data structures for on-line updating of minimum spanning trees}",
 172    journal = "{SIAM Journal on Computing}",
 173    volume = "14",
 174    pages = "781--798",
 175    year = "1985"
 176 }
 177
 178 @article { mm:mst,
 179    author = "Martin Mare\v{s}",
 180    title = "{Two linear time algorithms for MST on minor closed graph classes}",
 181    journal = "{Archivum Mathematicum}",
 182    volume = "40",
 183    pages = "315--320",
 184    year = "2004"
 185 }
 186
 187 @article{ ft:fibonacci,
 188  author = {Michael L. Fredman and Robert Endre Tarjan},
 189  title = {Fibonacci heaps and their uses in improved network optimization algorithms},
 190  journal = {J. ACM},
 191  volume = {34},
 192  number = {3},
 193  year = {1987},
 194  issn = {0004-5411},
 195  pages = {596--615},
 196  doi = {http://doi.acm.org/10.1145/28869.28874},
 197  publisher = {ACM Press},
 198  address = {New York, NY, USA},
 199  }
 200
 201 @article{ komlos:verify,
 202   author    = {J{\'a}nos Koml{\'o}s},
 203   title     = {Linear verification for spanning trees.},
 204   journal   = {Combinatorica},
 205   volume    = {5},
 206   number    = {1},
 207   year      = {1985},
 208   pages     = {57--65},
 209   bibsource = {DBLP, http://dblp.uni-trier.de}
 210 }
 211
 212 @inproceedings{ king:verify,
 213     author = "Valerie King",
 214     title = "A Simpler Minimum Spanning Tree Verification Algorithm",
 215     booktitle = "Workshop on Algorithms and Data Structures",
 216     pages = "440--448",
 217     year = "1995",
 218     url = "citeseer.ist.psu.edu/king95simpler.html" }
 219
 220 @book { schrijver,
 221     author = "Alexander Schrijver",
 222     title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
 223     series = "Algorithms and Combinatorics",
 224     volume = 24,
 225     year = 2003,
 226     publisher = "Springer Verlag"
 227 }
 228
 229 @inproceedings{ thorup:ac0,
 230  author = {Mikkel Thorup},
 231  title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
 232  booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
 233  year = {2003},
 234  isbn = {0-89871-538-5},
 235  pages = {699--707},
 236  location = {Baltimore, Maryland},
 237  publisher = {Society for Industrial and Applied Mathematics},
 238  address = {Philadelphia, PA, USA},
 239 }
 240
 241 @article{ kruskal:mst,
 242   title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
 243   author={Kruskal Jr, J.B.},
 244   journal={Proceedings of the American Mathematical Society},
 245   volume={7},
 246   number={1},
 247   pages={48--50},
 248   year={1956},
 249   publisher={JSTOR}
 250 }
 251
 252 @book{ diestel:gt,
 253   title={{Graph Theory}},
 254   author={Diestel, R.},
 255   year={2005},
 256   publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K}
 257 }
 258
 259 @article{ thorup:pq,
 260   title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
 261   author={Thorup, M.},
 262   journal={Proceedings of the thirty-fifth ACM symposium on Theory of computing},
 263   pages={149--158},
 264   year={2003},
 265   publisher={ACM Press New York, NY, USA}
 266 }