ga.bib

   1 @inproceedings{ alstrup98marked,
   2     author = "Stephen Alstrup and Thore Husfeldt and Theis Rauhe",
   3     title = "Marked Ancestor Problems",
   4     booktitle = "{IEEE} Symposium on Foundations of Computer Science",
   5     pages = "534--544",
   6     year = "1998",
   7     url = "citeseer.ist.psu.edu/alstrup98marked.html" }
   8
   9 @inproceedings{ bender00lca,
  10     author = "Michael A. Bender and Martin Farach-Colton",
  11     title = "The {LCA} Problem Revisited",
  12     booktitle = "Latin American Theoretical {INformatics}",
  13     pages = "88-94",
  14     year = "2000",
  15     url = "citeseer.ist.psu.edu/bender00lca.html" }
  16
  17 @inproceedings{ frederickson91ambivalent,
  18     author = "Greg N. Frederickson",
  19     title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees",
  20     booktitle = "{IEEE} Symposium on Foundations of Computer Science",
  21     pages = "632-641",
  22     year = "1991",
  23     url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" }
  24
  25 @article{ tarjan84setunion,
  26  author = {Robert E. Tarjan and Jan van Leeuwen},
  27  title = {Worst-case Analysis of Set Union Algorithms},
  28  journal = {J. ACM},
  29  volume = {31},
  30  number = {2},
  31  year = {1984},
  32  issn = {0004-5411},
  33  pages = {245--281},
  34  doi = {http://doi.acm.org/10.1145/62.2160},
  35  publisher = {ACM Press},
  36  address = {New York, NY, USA},
  37 }
  38
  39 @article{ alstrup97optimal,
  40     author = "Stephen Alstrup and Jens P. Secher and Maz Spork",
  41     title = "Optimal On-Line Decremental Connectivity in Trees",
  42     journal = "Information Processing Letters",
  43     volume = "64",
  44     number = "4",
  45     pages = "161-164",
  46     year = "1997",
  47     url = "citeseer.ist.psu.edu/alstrup97optimal.html" }
  48
  49 @inproceedings{ karkkainen03simple,
  50   author = "J. K{\"a}rkk{\"a}inen and P. Sanders",
  51   title = "Simple linear work suffix array construction",
  52   booktitle = "Proc. 13th International Conference on Automata, Languages and Programming",
  53   publisher = "Springer Verlag",
  54   year = "2003",
  55   url = "citeseer.ist.psu.edu/arkk03simple.html" }
  56
  57 @article{ ukkonen95line,
  58     author = "Esko Ukkonen",
  59     title = "On-Line Construction of Suffix Trees",
  60     journal = "Algorithmica",
  61     volume = "14",
  62     number = "3",
  63     pages = "249--260",
  64     year = "1995",
  65     url = "citeseer.ist.psu.edu/ukkonen95line.html" }
  66
  67 @inproceedings { fw90trans,
  68    author = "M. Fredman and D. E. Willard",
  69    title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}",
  70    booktitle = "{Proceedings of FOCS'90}",
  71    pages = "719--725",
  72    year = "1990"
  73 }
  74
  75 @article{boas77,
  76   author    = {Peter van Emde Boas},
  77   title     = {Preserving Order in a Forest in Less Than Logarithmic Time
  78                and Linear Space.},
  79   journal   = {Inf. Process. Lett.},
  80   volume    = {6},
  81   number    = {3},
  82   year      = {1977},
  83   pages     = {80-82},
  84   bibsource = {DBLP, http://dblp.uni-trier.de}
  85 }
  86
  87 @inproceedings{thorup03ac0,
  88  author = {Mikkel Thorup},
  89  title = {On AC0 implementations of fusion trees and atomic heaps},
  90  booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
  91  year = {2003},
  92  isbn = {0-89871-538-5},
  93  pages = {699--707},
  94  location = {Baltimore, Maryland},
  95  publisher = {Society for Industrial and Applied Mathematics},
  96  address = {Philadelphia, PA, USA},
  97  }
  98
  99 @article{ benamram95what,
 100     author = "Ben-Amram",
 101     title = "What is a ``Pointer Machine''?",
 102     journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
 103     volume = "26",
 104     year = "1995",
 105     url = "citeseer.ist.psu.edu/ben-amram95what.html" }
 106
 107 @unpublished { demaine,
 108  author = "Erik Demaine",
 109  title = "{Advanced Data Structures}",
 110  note = "{MIT Lecture Notes}",
 111  year = 2005
 112 }
 113
 114 @article{ matsui:planar,
 115     author = "Tomomi Matsui",
 116     title = "{The Minimum Spanning tree Problem on a Planar Graph}",
 117     journal = "Discrete Applied Mathematics",
 118     volume = "58",
 119     year = "1995",
 120     pages = "91--94",
 121     url = "citeseer.nj.nec.com/2319.html"
 122 }
 123
 124 @article{ chazelle:ackermann,
 125     author = "Bernard Chazelle",
 126     title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
 127     journal = jacm,
 128     volume = "47",
 129     pages = "1028--1047",
 130     year = "2000"
 131 }
 132
 133 @article{ nesetril:history,
 134     author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
 135     title = "{Some remarks on the history of MST-problem}",
 136     journal = "Archivum Mathematicum",
 137     volume = "33",
 138     pages = "15--22",
 139     year = "1997"
 140 }
 141
 142 @article{ nesetril:boruvka,
 143     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
 144     title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
 145     journal = "Discrete Mathematics",
 146     volume = "233(1--3)",
 147     pages = "3--36",
 148     year = "2001"
 149 }
 150
 151 @unpublished { nesetril:minors,
 152     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
 153     title = "{Colorings and Homomorphism of Minor Closed Classes}",
 154     note = "To appear in {\it Pollack-Goodman Festschrift,} Springer Verlag, 2002."
 155 }
 156
 157 @article { boruvka:ojistem,
 158     author = "Otakar Bor{\accent23u}vka",
 159     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
 160     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
 161     volume = "III",
 162     year = "1926",
 163     pages = "37--58",
 164     note = "Czech with German summary"
 165 }
 166
 167 @book { tarjan:dsna,
 168     author = "Robert E. Tarjan",
 169     title = "{Data structures and network algorithms}",
 170     series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}",
 171     volume = 44,
 172     year = "1983",
 173     publisher = "SIAM"
 174 }
 175
 176 @article { gh:history,
 177     author = "R. L. Graham and P. Hell",
 178     title = "{On the history of the minimum spanning tree problem}",
 179     journal = "{Annals of the History of Computing}",
 180     volume = "7",
 181     year = "1985",
 182     pages = "43--57"
 183 }
 184
 185 @techreport { pettie:ackermann,
 186     author = "Seth Pettie",
 187     title = "{Finding minimum spanning trees in $O(m\alpha(m,n))$ time}",
 188     institution = "Univ. of Texas at Austin",
 189     year = "1999",
 190     number = "TR99-23",
 191     type = "Tech Report"
 192 }
 193
 194 @inproceedings { pettie:optimal,
 195    author = "Seth Pettie and Vijaya Ramachandran",
 196    title = "{An Optimal Minimum Spanning Tree Algorithm}",
 197    booktitle = "{Proceedings of ICALP'2000}",
 198    year = "2000",
 199    publisher = "Springer Verlag",
 200    pages = "49--60"
 201 }
 202
 203 @article { karger:randomized,
 204    author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
 205    title = "{Linear expected-time algorithms for connectivity problems}",
 206    journal = jacm,
 207    volume = "42",
 208    pages = "321--328",
 209    year = "1995"
 210 }
 211
 212 @article { frederickson:online,
 213    author = "Greg N. Frederickson",
 214    title = "{Data structures for on-line updating of minimum spanning trees}",
 215    journal = "{SIAM Journal on Computing}",
 216    volume = "14",
 217    pages = "781--798",
 218    year = "1985"
 219 }
 220
 221 @article { mm:mst,
 222    author = "Martin Mare\v{s}",
 223    title = "{Two linear time algorithms for MST on minor closed graph classes}",
 224    journal = "{Archivum Mathematicum}",
 225    volume = "40",
 226    pages = "315--320",
 227    year = "2004"
 228 }
 229
 230 @article{ ft:fibonacci,
 231  author = {Michael L. Fredman and Robert Endre Tarjan},
 232  title = {Fibonacci heaps and their uses in improved network optimization algorithms},
 233  journal = {J. ACM},
 234  volume = {34},
 235  number = {3},
 236  year = {1987},
 237  issn = {0004-5411},
 238  pages = {596--615},
 239  doi = {http://doi.acm.org/10.1145/28869.28874},
 240  publisher = {ACM Press},
 241  address = {New York, NY, USA},
 242  }
 243
 244 @article{ komlos:verify,
 245   author    = {J{\'a}nos Koml{\'o}s},
 246   title     = {Linear verification for spanning trees.},
 247   journal   = {Combinatorica},
 248   volume    = {5},
 249   number    = {1},
 250   year      = {1985},
 251   pages     = {57--65},
 252   bibsource = {DBLP, http://dblp.uni-trier.de}
 253 }
 254
 255 @inproceedings{ king:verify,
 256     author = "Valerie King",
 257     title = "A Simpler Minimum Spanning Tree Verification Algorithm",
 258     booktitle = "Workshop on Algorithms and Data Structures",
 259     pages = "440--448",
 260     year = "1995",
 261     url = "citeseer.ist.psu.edu/king95simpler.html" }
 262
 263 @article{ gomoryhu,
 264    author = "R. E. Gomory and T. C. Hu",
 265    title = "Multi-Terminal Network Flows",
 266    journal = "{Journal of SIAM}",
 267    volume = {9},
 268    number = {4},
 269    year = {1961},
 270    pages = {551--570}
 271 }
 272
 273 @article{ nagaiba:conn,
 274  author = {Hiroshi Nagamochi and Toshihide Ibaraki},
 275  title = {Computing edge-connectivity in multigraphs and capacitated graphs},
 276  journal = {SIAM J. Discret. Math.},
 277  volume = {5},
 278  number = {1},
 279  year = {1992},
 280  issn = {0895-4801},
 281  pages = {54--66},
 282  doi = {http://dx.doi.org/10.1137/0405004},
 283  publisher = {Society for Industrial and Applied Mathematics},
 284  address = {Philadelphia, PA, USA},
 285  }
 286
 287 @article{ alon:matching,
 288  author = {Noga Alon},
 289  title = {A simple algorithm for edge-coloring bipartite multigraphs},
 290  journal = {Inf. Process. Lett.},
 291  volume = {85},
 292  number = {6},
 293  year = {2003},
 294  issn = {0020-0190},
 295  pages = {301--302},
 296  doi = {http://dx.doi.org/10.1016/S0020-0190(02)00446-5},
 297  publisher = {Elsevier North-Holland, Inc.},
 298  address = {Amsterdam, The Netherlands, The Netherlands},
 299  }
 300
 301 @book { kapitoly,
 302     author = "Ji\v{r}\'\i{} Matou\v{s}ek and Jaroslav Ne\v{s}et\v{r}il",
 303     title = "{Kapitoly z~diskr\'etn\'\i{} matematiky}",
 304     year = "2002",
 305     publisher = "Karolinum",
 306     address = "Praha"
 307 }
 308
 309 @book { demel,
 310     author = "Ji\v{r}\'\i{} Demel",
 311     title = "{Grafy a jejich aplikace}",
 312     year = 2002,
 313     publisher = "Academia",
 314     address = "Praha"
 315 }
 316
 317 @book { schrijver,
 318     author = "Alexander Schrijver",
 319     title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
 320     series = "Algorithms and Combinatorics",
 321     volume = 24,
 322     year = 2003,
 323     publisher = "Springer Verlag"
 324 }
 325
 326 @book { kucera,
 327     author = "Lud'ek Ku\v{c}era",
 328     title = "{Kombinatorick\'e algoritmy}",
 329     year = 1989,
 330     publisher = "SNTL",
 331     address = "Praha"
 332 }
 333
 334 @article{ boyer:cutting,
 335   title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
 336   author={Boyer, J.M. and Myrvold, W.J.},
 337   journal={Journal of Graph Algorithms and Applications},
 338   volume={8},
 339   number={3},
 340   pages={241--273},
 341   year={2004}
 342 }
 343
 344 @article{ tarjan:planarity,
 345   title={{Efficient Planarity Testing}},
 346   author={Hopcroft, J. and Tarjan, R.},
 347   journal={Journal of the ACM (JACM)},
 348   volume={21},
 349   number={4},
 350   pages={549--568},
 351   year={1974},
 352   publisher={ACM Press New York, NY, USA}
 353 }
 354
 355 @article{ schnyder:grid,
 356   title={{Embedding planar graphs on the grid}},
 357   author={Schnyder, W.},
 358   journal={Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms},
 359   pages={138--148},
 360   year={1990},
 361   publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
 362 }
 363
 364 @article{ chrobak:grid,
 365   title={{A linear-time algorithm for drawing a planar graph on a grid}},
 366   author={Chrobak, M. and Payne, T. H.},
 367   journal={Information Processing Letters},
 368   volume={54},
 369   number={4},
 370   pages={241--246},
 371   year={1995},
 372   publisher={Elsevier Science}
 373 }
 374
 375 @inproceedings{ thorup:ac0,
 376  author = {Mikkel Thorup},
 377  title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
 378  booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
 379  year = {2003},
 380  isbn = {0-89871-538-5},
 381  pages = {699--707},
 382  location = {Baltimore, Maryland},
 383  publisher = {Society for Industrial and Applied Mathematics},
 384  address = {Philadelphia, PA, USA},
 385 }
 386
 387 @article{ kruskal:mst,
 388   title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
 389   author={Kruskal Jr, J.B.},
 390   journal={Proceedings of the American Mathematical Society},
 391   volume={7},
 392   number={1},
 393   pages={48--50},
 394   year={1956},
 395   publisher={JSTOR}
 396 }
 397
 398 @book{ diestel:gt,
 399   title={{Graph Theory}},
 400   author={Diestel, R.},
 401   year={2005},
 402   publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K}
 403 }
 404
 405 @article{ thorup:usssp,
 406   title={{Undirected single-source shortest paths with positive integer weights in linear time}},
 407   author={Thorup, M.},
 408   journal={Journal of the ACM (JACM)},
 409   volume={46},
 410   number={3},
 411   pages={362--394},
 412   year={1999},
 413   publisher={ACM Press New York, NY, USA}
 414 }
 415
 416 @article{ thorup:pq,
 417   title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
 418   author={Thorup, M.},
 419   journal={Proceedings of the thirty-fifth ACM symposium on Theory of computing},
 420   pages={149--158},
 421   year={2003},
 422   publisher={ACM Press New York, NY, USA}
 423 }
 424
 425 @article{ thorup:isort,
 426   title={{Integer Sorting in 0 (n sqrt (log log n)) Expected Time and Linear Space}},
 427   author={Han, Y. and Thorup, M.},
 428   journal={Proceedings of the 43rd Symposium on Foundations of Computer Science},
 429   pages={135--144},
 430   year={2002},
 431   publisher={IEEE Computer Society Washington, DC, USA}
 432 }
 433
 434 @article{ han:sort,
 435   title={{Deterministic sorting in O (nloglogn) time and linear space}},
 436   author={Han, Y.},
 437   journal={Journal of Algorithms},
 438   volume={50},
 439   number={1},
 440   pages={96--105},
 441   year={2004},
 442   publisher={Elsevier}
 443 }
 444
 445 @techreport{ burrows:bwt,
 446   title={{A block-sorting lossless data compression algorithm}},
 447   author={Burrows, M. and Wheeler, D.J.},
 448   year={1994},
 449   number={124},
 450   institution={Digital Systems Research Center}
 451 }