@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",
publisher = "SNTL",
address = "Praha"
}
+
+@article{ boyer:cutting,
+ title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
+ author={Boyer, J.M. and Myrvold, W.J.},
+ journal={Journal of Graph Algorithms and Applications},
+ volume={8},
+ number={3},
+ pages={241--273},
+ year={2004}
+}
+
+@article{ tarjan:planarity,
+ title={{Efficient Planarity Testing}},
+ author={Hopcroft, J. and Tarjan, R.},
+ journal={Journal of the ACM (JACM)},
+ volume={21},
+ number={4},
+ pages={549--568},
+ year={1974},
+ publisher={ACM Press New York, NY, USA}
+}
+
+@article{ schnyder:grid,
+ title={{Embedding planar graphs on the grid}},
+ author={Schnyder, W.},
+ journal={Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms},
+ pages={138--148},
+ year={1990},
+ publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
+}
+
+@article{ chrobak:grid,
+ title={{A linear-time algorithm for drawing a planar graph on a grid}},
+ author={Chrobak, M. and Payne, T. H.},
+ journal={Information Processing Letters},
+ volume={54},
+ number={4},
+ pages={241--246},
+ year={1995},
+ publisher={Elsevier Science}
+}
+
+@inproceedings{ thorup:ac0,
+ author = {Mikkel Thorup},
+ title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
+ booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
+ year = {2003},
+ isbn = {0-89871-538-5},
+ pages = {699--707},
+ location = {Baltimore, Maryland},
+ publisher = {Society for Industrial and Applied Mathematics},
+ address = {Philadelphia, PA, USA},
+}
+
+@article{ kruskal:mst,
+ title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
+ author={Kruskal Jr, J.B.},
+ journal={Proceedings of the American Mathematical Society},
+ volume={7},
+ number={1},
+ pages={48--50},
+ year={1956},
+ publisher={JSTOR}
+}
+
+@book{ diestel:gt,
+ title={{Graph Theory}},
+ author={Diestel, R.},
+ 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},
+}
+
+@article{ haeupler:rankph,
+ title={Rank-pairing heaps},
+ author={Haeupler, B. and Sen, S. and Tarjan, R.},
+ journal={Algorithms-ESA 2009},
+ pages={659--670},
+ year={2009},
+ publisher={Springer}
+}
+
+@article{ elmasry:violheap,
+ title={{The violation heap: a relaxed Fibonacci-like heap}},
+ author={Elmasry, A.},
+ journal={Computing and Combinatorics},
+ pages={479--488},
+ year={2010},
+ publisher={Springer}
+}
+
+@inproceedings{ fredman:cellprobe,
+ author = {M. Fredman and M. Saks},
+ title = {The cell probe complexity of dynamic data structures},
+ booktitle = {STOC '89: Proceedings of the 21st annual ACM Symposium on Theory of Computing},
+ year = {1989},
+ isbn = {0-89791-307-8},
+ pages = {345--354},
+ location = {Seattle, Washington, United States},
+ doi = {http://doi.acm.org/10.1145/73007.73040},
+}
+
+@inproceedings{ alstrup:worstuf,
+ title={Worst-case and amortised optimality in union-find},
+ author={Alstrup, S. and Ben-Amram, A.M. and Rauhe, T.},
+ booktitle={Proceedings of the 31st annual ACM symposium on Theory of computing},
+ pages={499--506},
+ year={1999},
+ organization={ACM}
+}
+
+@article{ rs:wagner,
+ title={{Graph minors: XX. Wagner's Conjecture}},
+ author={Robertson, N. and Seymour, P. D.},
+ journal={Journal of Combinatorial Theory Series B},
+ volume={92},
+ number={2},
+ pages={325--357},
+ year={2004},
+}
projects / ga.git / blobdiff