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 }
 452
 453 @article{ weihe:paths,
 454   title={{Edge-Disjoint $(s,t)$-Paths in Undirected Planar Graphs in Linear Time}},
 455   author={Weihe, K.},
 456   journal={Journal of Algorithms},
 457   volume={23},
 458   number={1},
 459   pages={121--138},
 460   year={1997},
 461   publisher={Elsevier}
 462 }
 463
 464 @article{ threeinds,
 465   title={{An $\O({\vert V\vert}^3)$ algorithm for finding maximum flows in networks}},
 466   author={Malhotra, V. and Kumar, M.P. and Maheshwari, S.N.},
 467   journal={Information Processing Letters},
 468   volume={7},
 469   number={6},
 470   pages={277--278},
 471   year={1978}
 472 }
 473
 474 @article{ ahomcc,
 475   title={{Efficient string matching: an aid to bibliographic search}},
 476   author={Aho, A.V. and Corasick, M.J.},
 477   journal={Communications of the ACM},
 478   volume={18},
 479   number={6},
 480   pages={333--340},
 481   year={1975},
 482   publisher={ACM Press New York, NY, USA}
 483 }
 484
 485 @article{ hopcroft:matching,
 486   title={{An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs}},
 487   author={Hopcroft, J.E. and Karp, R.M.},
 488   journal={SIAM Journal on Computing},
 489   volume={2},
 490   number={4},
 491   pages={225--231},
 492   year={1973}
 493 }
 494
 495 @article{ karger:mincut,
 496  author = {Karger, David R. and Stein, Clifford},
 497  title = {A new approach to the minimum cut problem},
 498  journal = {J. ACM},
 499  volume = {43},
 500  number = {4},
 501  year = {1996},
 502  issn = {0004-5411},
 503  pages = {601--640},
 504  doi = {http://doi.acm.org/10.1145/234533.234534},
 505  publisher = {ACM},
 506  address = {New York, NY, USA},
 507 }
 508
 509 @inproceedings{ thorup:queue,
 510   title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
 511   author={Thorup, M.},
 512   booktitle={Proceedings of the thirty-fifth annual ACM symposium on Theory of computing},
 513   pages={149--158},
 514   year={2003},
 515 }
 516
 517 @article{ thorup:equiv,
 518   title={{Equivalence between priority queues and sorting}},
 519   author={Thorup, M.},
 520   journal={Journal of the ACM},
 521   volume={54},
 522   number={6},
 523   pages={28},
 524   year={2007},
 525   publisher={ACM}
 526 }
 527
 528 @conference{ cherkassky:hotq,
 529   title={{Buckets, heaps, lists, and monotone priority queues}},
 530   author={Cherkassky, B.V. and Goldberg, A.V. and Silverstein, C.},
 531   booktitle={Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms},
 532   pages={83--92},
 533   year={1997},
 534   organization={Society for Industrial and Applied Mathematics}
 535 }
 536
 537 @article{ bellman:bfm,
 538    author = {Richard Bellman},
 539    title = {On a Routing Problem},
 540    journal = {Quarterly of Applied Mathematics},
 541    volume = {16},
 542    number = {1},
 543    year = {1958},
 544    pages = {87--90},
 545    url = {http://wisl.ece.cornell.edu/ECE794/Jan29/bellman1958.pdf},
 546 }
 547
 548 @techreport{ ford:bfm,
 549    title = {Network Flow Theory},
 550    author = {Ford Jr., L. R.},
 551    institution = {The RAND Corperation, Santa Moncia, California},
 552    number = {P-923},
 553    month = {August},
 554    type = {Paper},
 555    year = {1956},
 556 }
 557
 558 @article{ dijkstra:mstandpath,
 559   title={{A note on two problems in connexion with graphs}},
 560   author = "Dijkstra, E. W.",
 561   journal={Numerische Mathematik},
 562   volume={1},
 563   number={1},
 564   pages={269--271},
 565   year={1959},
 566   publisher={Springer Verlag}
 567 }
 568
 569 @article{ goldberg:mlb,
 570   title={{Implementations of Dijkstra's algorithm based on multi-level buckets}},
 571   author={Goldberg, A.V. and Silverstein, C.},
 572   journal={Network optimization},
 573   pages={292--327},
 574   year={1997},
 575   publisher={Springer Verlag}
 576 }
 577
 578 @article{ hart:astar,
 579   title={{Correction to a formal basis for the heuristic determination of minimum cost paths}},
 580   author={Hart, P.E. and Nilsson, N.J. and Raphael, B.},
 581   journal={ACM SIGART Bulletin},
 582   number={37},
 583   pages={28--29},
 584   issn={0163-5719},
 585   year={1972},
 586   publisher={ACM}
 587 }
 588
 589 @article{ coppersmith:matmult,
 590   title={{Matrix multiplication via arithmetic progressions}},
 591   author={Coppersmith, D. and Winograd, S.},
 592   journal={Journal of symbolic computation},
 593   volume={9},
 594   number={3},
 595   pages={251--280},
 596   issn={0747-7171},
 597   year={1990},
 598   publisher={Elsevier}
 599 }
 600
 601 @article{ strassen:matmult,
 602   title={{Gaussian elimination is not optimal}},
 603   author={Strassen, V.},
 604   journal={Numerische Mathematik},
 605   volume={13},
 606   number={4},
 607   pages={354--356},
 608   issn={0029-599X},
 609   year={1969},
 610   publisher={Springer}
 611 }
 612
 613 @article{ szegedy:matmult,
 614     author = {Cohn, Henry and Kleinberg, Robert and Szegedy, Balazs and Umans, Christopher},
 615     citeulike-article-id = {8349164},
 616     citeulike-linkout-0 = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.39},
 617     citeulike-linkout-1 = {http://dx.doi.org/10.1109/SFCS.2005.39},
 618     doi = {10.1109/SFCS.2005.39},
 619     isbn = {0-7695-2468-0},
 620     journal = {Foundations of Computer Science, Annual IEEE Symposium on},
 621     keywords = {algebraic, complexity, matrix, multiplication},
 622     pages = {379--388},
 623     posted-at = {2010-12-02 18:55:57},
 624     priority = {3},
 625     publisher = {IEEE Computer Society},
 626     title = {{Group-theoretic Algorithms for Matrix Multiplication}},
 627     url = {http://dx.doi.org/10.1109/SFCS.2005.39},
 628     year = {2005}
 629 }
 630
 631 @article{ zwick:apsp,
 632     author = {Zwick, Uri},
 633     citeulike-article-id = {1027459},
 634     citeulike-linkout-0 = {http://dx.doi.org/10.1007/s00453-005-1199-1},
 635     citeulike-linkout-1 = {http://www.ingentaconnect.com/content/klu/453/2006/00000046/00000002/00001199},
 636     doi = {10.1007/s00453-005-1199-1},
 637     issn = {0178-4617},
 638     journal = {Algorithmica},
 639     month = {October},
 640     number = {2},
 641     pages = {181--192},
 642     posted-at = {2007-01-06 00:46:43},
 643     publisher = {Springer},
 644     title = {{A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths}},
 645     url = {http://dx.doi.org/10.1007/s00453-005-1199-1},
 646     volume = {46},
 647     year = {2006}
 648 }
 649
 650 @article{ chan:apsp,
 651     author = {Chan, Timothy},
 652     citeulike-article-id = {2315328},
 653     citeulike-linkout-0 = {http://dx.doi.org/10.1007/s00453-007-9062-1},
 654     doi = {10.1007/s00453-007-9062-1},
 655     journal = {Algorithmica},
 656     keywords = {algorithms, graph},
 657     month = {February},
 658     number = {2},
 659     pages = {236--243},
 660     posted-at = {2008-01-31 15:49:43},
 661     priority = {2},
 662     title = {{All-Pairs Shortest Paths with Real Weights in $O(n^3/\log n)$ Time}},
 663     url = {http://dx.doi.org/10.1007/s00453-007-9062-1},
 664     volume = {50},
 665     year = {2008}
 666 }
 667
 668 @article{ fredman:apsp,
 669   title={{New bounds on the complexity of the shortest path problem}},
 670   author={Fredman, M.L.},
 671   journal={SIAM Journal on Computing},
 672   volume={5},
 673   pages={83},
 674   year={1976}
 675 }
 676
 677 @article{ zwick:apspint,
 678   title={{All pairs shortest paths using bridging sets and rectangular matrix multiplication}},
 679   author={Zwick, U.},
 680   journal={Journal of the ACM (JACM)},
 681   volume={49},
 682   number={3},
 683   pages={289--317},
 684   issn={0004-5411},
 685   year={2002},
 686   publisher={ACM}
 687 }
 688
 689 @inproceedings{ seidel:unitlength,
 690  author = {Seidel, Raimund},
 691  title = {On the all-pairs-shortest-path problem},
 692  booktitle = {Proceedings of the twenty-fourth annual ACM symposium on Theory of computing},
 693  year = {1992},
 694  isbn = {0-89791-511-9},
 695  location = {Victoria, British Columbia, Canada},
 696  pages = {745--749},
 697  numpages = {5},
 698  url = {http://doi.acm.org/10.1145/129712.129784},
 699  doi = {http://doi.acm.org/10.1145/129712.129784},
 700  acmid = {129784},
 701  publisher = {ACM},
 702 }
 703
 704 @article{ haeupler:rankph,
 705   title={Rank-pairing heaps},
 706   author={Haeupler, B. and Sen, S. and Tarjan, R.},
 707   journal={Algorithms-ESA 2009},
 708   pages={659--670},
 709   year={2009},
 710   publisher={Springer}
 711 }
 712
 713 @article{ elmasry:violheap,
 714   title={{The violation heap: a relaxed Fibonacci-like heap}},
 715   author={Elmasry, A.},
 716   journal={Computing and Combinatorics},
 717   pages={479--488},
 718   year={2010},
 719   publisher={Springer}
 720 }
 721
 722 @inproceedings{ fredman:cellprobe,
 723   author = {M. Fredman and M. Saks},
 724   title = {The cell probe complexity of dynamic data structures},
 725   booktitle = {STOC '89: Proceedings of the 21st annual ACM Symposium on Theory of Computing},
 726   year = {1989},
 727   isbn = {0-89791-307-8},
 728   pages = {345--354},
 729   location = {Seattle, Washington, United States},
 730   doi = {http://doi.acm.org/10.1145/73007.73040},
 731 }
 732
 733 @inproceedings{ alstrup:worstuf,
 734   title={Worst-case and amortised optimality in union-find},
 735   author={Alstrup, S. and Ben-Amram, A.M. and Rauhe, T.},
 736   booktitle={Proceedings of the 31st annual ACM symposium on Theory of computing},
 737   pages={499--506},
 738   year={1999},
 739   organization={ACM}
 740 }
 741
 742 @article{ rs:wagner,
 743   title={{Graph minors: XX. Wagner's Conjecture}},
 744   author={Robertson, N. and Seymour, P. D.},
 745   journal={Journal of Combinatorial Theory Series B},
 746   volume={92},
 747   number={2},
 748   pages={325--357},
 749   year={2004},
 750 }
 751
 752 @inproceedings{ williams:matmult,
 753   title={{Multiplying matrices faster than Coppersmith-Winograd}},
 754   author={{Williams, V. V.}},
 755   booktitle={STOC '12: Proceedings of the 44th annual ACM Symposium on Theory of Computing},
 756   pages={887--898},
 757   year = {2012},
 758 }
 759
 760 @inproceedings{ raz:mmlower,
 761   title={{On the complexity of matrix product}},
 762   author={{Raz, R.}},
 763   booktitle={STOC '02: Proceedings of the 34th annual ACM Symposium on Theory of Computing},
 764   pages={144-151},
 765   year = {2002},
 766 }