X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=ga.bib;h=74bc27ecba48df4c797fa5a9896b1e49d12ca512;hb=87823c08e3c0218717e8d6f5b51568c85e813e0d;hp=d13924dea301a4fd874b4880202b9a5120db0ba7;hpb=9bac2068725934a69d4ae16e499df4873976455c;p=ga.git

diff --git a/ga.bib b/ga.bib
index d13924d..74bc27e 100644
--- a/ga.bib
+++ b/ga.bib
@@ -16,7 +16,7 @@
 
 @inproceedings{ frederickson91ambivalent,
     author = "Greg N. Frederickson",
-    title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees",
+    title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
     booktitle = "{IEEE} Symposium on Foundations of Computer Science",
     pages = "632-641",
     year = "1991",
@@ -401,3 +401,302 @@
   year={2005},
   publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K}
 }
+
+@article{ thorup:usssp,
+  title={{Undirected single-source shortest paths with positive integer weights in linear time}},
+  author={Thorup, M.},
+  journal={Journal of the ACM (JACM)},
+  volume={46},
+  number={3},
+  pages={362--394},
+  year={1999},
+  publisher={ACM Press New York, NY, USA}
+}
+
+@article{ thorup:pq,
+  title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
+  author={Thorup, M.},
+  journal={Proceedings of the thirty-fifth ACM symposium on Theory of computing},
+  pages={149--158},
+  year={2003},
+  publisher={ACM Press New York, NY, USA}
+}
+
+@article{ thorup:isort,
+  title={{Integer Sorting in 0 (n sqrt (log log n)) Expected Time and Linear Space}},
+  author={Han, Y. and Thorup, M.},
+  journal={Proceedings of the 43rd Symposium on Foundations of Computer Science},
+  pages={135--144},
+  year={2002},
+  publisher={IEEE Computer Society Washington, DC, USA}
+}
+
+@article{ han:sort,
+  title={{Deterministic sorting in O (nloglogn) time and linear space}},
+  author={Han, Y.},
+  journal={Journal of Algorithms},
+  volume={50},
+  number={1},
+  pages={96--105},
+  year={2004},
+  publisher={Elsevier}
+}
+
+@techreport{ burrows:bwt,
+  title={{A block-sorting lossless data compression algorithm}},
+  author={Burrows, M. and Wheeler, D.J.},
+  year={1994},
+  number={124},
+  institution={Digital Systems Research Center}
+}
+
+@article{ weihe:paths,
+  title={{Edge-Disjoint $(s,t)$-Paths in Undirected Planar Graphs in Linear Time}},
+  author={Weihe, K.},
+  journal={Journal of Algorithms},
+  volume={23},
+  number={1},
+  pages={121--138},
+  year={1997},
+  publisher={Elsevier}
+}
+
+@article{ threeinds,
+  title={{An $\O({\vert V\vert}^3)$ algorithm for finding maximum flows in networks}},
+  author={Malhotra, V. and Kumar, M.P. and Maheshwari, S.N.},
+  journal={Information Processing Letters},
+  volume={7},
+  number={6},
+  pages={277--278},
+  year={1978}
+}
+
+@article{ ahomcc,
+  title={{Efficient string matching: an aid to bibliographic search}},
+  author={Aho, A.V. and Corasick, M.J.},
+  journal={Communications of the ACM},
+  volume={18},
+  number={6},
+  pages={333--340},
+  year={1975},
+  publisher={ACM Press New York, NY, USA}
+}
+
+@article{ hopcroft:matching,
+  title={{An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs}},
+  author={Hopcroft, J.E. and Karp, R.M.},
+  journal={SIAM Journal on Computing},
+  volume={2},
+  number={4},
+  pages={225--231},
+  year={1973}
+}
+
+@article{ karger:mincut,
+ author = {Karger, David R. and Stein, Clifford},
+ title = {A new approach to the minimum cut problem},
+ journal = {J. ACM},
+ volume = {43},
+ number = {4},
+ year = {1996},
+ issn = {0004-5411},
+ pages = {601--640},
+ doi = {http://doi.acm.org/10.1145/234533.234534},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
+
+@inproceedings{ thorup:queue,
+  title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
+  author={Thorup, M.},
+  booktitle={Proceedings of the thirty-fifth annual ACM symposium on Theory of computing},
+  pages={149--158},
+  year={2003},
+}
+
+@article{ thorup:equiv,
+  title={{Equivalence between priority queues and sorting}},
+  author={Thorup, M.},
+  journal={Journal of the ACM},
+  volume={54},
+  number={6},
+  pages={28},
+  year={2007},
+  publisher={ACM}
+}
+
+@conference{ cherkassky:hotq,
+  title={{Buckets, heaps, lists, and monotone priority queues}},
+  author={Cherkassky, B.V. and Goldberg, A.V. and Silverstein, C.},
+  booktitle={Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms},
+  pages={83--92},
+  year={1997},
+  organization={Society for Industrial and Applied Mathematics}
+}
+
+@article{ bellman:bfm,
+   author = {Richard Bellman},
+   title = {On a Routing Problem},
+   journal = {Quarterly of Applied Mathematics},
+   volume = {16},
+   number = {1},
+   year = {1958},
+   pages = {87--90},
+   url = {http://wisl.ece.cornell.edu/ECE794/Jan29/bellman1958.pdf},
+}
+
+@techreport{ ford:bfm,
+   title = {Network Flow Theory},
+   author = {Ford Jr., L. R.},
+   institution = {The RAND Corperation, Santa Moncia, California},
+   number = {P-923},
+   month = {August},
+   type = {Paper},
+   year = {1956},
+}
+
+@article{ dijkstra:mstandpath,
+  title={{A note on two problems in connexion with graphs}},
+  author = "Dijkstra, E. W.",
+  journal={Numerische Mathematik},
+  volume={1},
+  number={1},
+  pages={269--271},
+  year={1959},
+  publisher={Springer Verlag}
+}
+
+@article{ goldberg:mlb,
+  title={{Implementations of Dijkstra's algorithm based on multi-level buckets}},
+  author={Goldberg, A.V. and Silverstein, C.},
+  journal={Network optimization},
+  pages={292--327},
+  year={1997},
+  publisher={Springer Verlag}
+}
+
+@article{ hart:astar,
+  title={{Correction to a formal basis for the heuristic determination of minimum cost paths}},
+  author={Hart, P.E. and Nilsson, N.J. and Raphael, B.},
+  journal={ACM SIGART Bulletin},
+  number={37},
+  pages={28--29},
+  issn={0163-5719},
+  year={1972},
+  publisher={ACM}
+}
+
+@article{ coppersmith:matmult,
+  title={{Matrix multiplication via arithmetic progressions}},
+  author={Coppersmith, D. and Winograd, S.},
+  journal={Journal of symbolic computation},
+  volume={9},
+  number={3},
+  pages={251--280},
+  issn={0747-7171},
+  year={1990},
+  publisher={Elsevier}
+}
+
+@article{ strassen:matmult,
+  title={{Gaussian elimination is not optimal}},
+  author={Strassen, V.},
+  journal={Numerische Mathematik},
+  volume={13},
+  number={4},
+  pages={354--356},
+  issn={0029-599X},
+  year={1969},
+  publisher={Springer}
+}
+
+@article{ szegedy:matmult,
+    author = {Cohn, Henry and Kleinberg, Robert and Szegedy, Balazs and Umans, Christopher},
+    citeulike-article-id = {8349164},
+    citeulike-linkout-0 = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.39},
+    citeulike-linkout-1 = {http://dx.doi.org/10.1109/SFCS.2005.39},
+    doi = {10.1109/SFCS.2005.39},
+    isbn = {0-7695-2468-0},
+    journal = {Foundations of Computer Science, Annual IEEE Symposium on},
+    keywords = {algebraic, complexity, matrix, multiplication},
+    pages = {379--388},
+    posted-at = {2010-12-02 18:55:57},
+    priority = {3},
+    publisher = {IEEE Computer Society},
+    title = {{Group-theoretic Algorithms for Matrix Multiplication}},
+    url = {http://dx.doi.org/10.1109/SFCS.2005.39},
+    year = {2005}
+}
+
+@article{ zwick:apsp,
+    author = {Zwick, Uri},
+    citeulike-article-id = {1027459},
+    citeulike-linkout-0 = {http://dx.doi.org/10.1007/s00453-005-1199-1},
+    citeulike-linkout-1 = {http://www.ingentaconnect.com/content/klu/453/2006/00000046/00000002/00001199},
+    doi = {10.1007/s00453-005-1199-1},
+    issn = {0178-4617},
+    journal = {Algorithmica},
+    month = {October},
+    number = {2},
+    pages = {181--192},
+    posted-at = {2007-01-06 00:46:43},
+    publisher = {Springer},
+    title = {{A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths}},
+    url = {http://dx.doi.org/10.1007/s00453-005-1199-1},
+    volume = {46},
+    year = {2006}
+}
+
+@article{ chan:apsp,
+    author = {Chan, Timothy},
+    citeulike-article-id = {2315328},
+    citeulike-linkout-0 = {http://dx.doi.org/10.1007/s00453-007-9062-1},
+    doi = {10.1007/s00453-007-9062-1},
+    journal = {Algorithmica},
+    keywords = {algorithms, graph},
+    month = {February},
+    number = {2},
+    pages = {236--243},
+    posted-at = {2008-01-31 15:49:43},
+    priority = {2},
+    title = {{All-Pairs Shortest Paths with Real Weights in $O(n^3/\log n)$ Time}},
+    url = {http://dx.doi.org/10.1007/s00453-007-9062-1},
+    volume = {50},
+    year = {2008}
+}
+
+@article{ fredman:apsp,
+  title={{New bounds on the complexity of the shortest path problem}},
+  author={Fredman, M.L.},
+  journal={SIAM Journal on Computing},
+  volume={5},
+  pages={83},
+  year={1976}
+}
+
+@article{ zwick:apspint,
+  title={{All pairs shortest paths using bridging sets and rectangular matrix multiplication}},
+  author={Zwick, U.},
+  journal={Journal of the ACM (JACM)},
+  volume={49},
+  number={3},
+  pages={289--317},
+  issn={0004-5411},
+  year={2002},
+  publisher={ACM}
+}
+
+@inproceedings{ seidel:unitlength,
+ author = {Seidel, Raimund},
+ title = {On the all-pairs-shortest-path problem},
+ booktitle = {Proceedings of the twenty-fourth annual ACM symposium on Theory of computing},
+ year = {1992},
+ isbn = {0-89791-511-9},
+ location = {Victoria, British Columbia, Canada},
+ pages = {745--749},
+ numpages = {5},
+ url = {http://doi.acm.org/10.1145/129712.129784},
+ doi = {http://doi.acm.org/10.1145/129712.129784},
+ acmid = {129784},
+ publisher = {ACM},
+}