X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=biblio.bib;h=304eb3cd27ad2dea9604638877eee3a7a3a17d7e;hb=e0ddb64ea79c2753f51ad2465c87ebfe1a75be4a;hp=02c69e6f34a920888d5ab8144fb78c6585c0f907;hpb=2e9f82a6570b037172319c1abe91d32f7d27fb83;p=saga.git diff --git a/biblio.bib b/biblio.bib index 02c69e6..304eb3c 100644 --- a/biblio.bib +++ b/biblio.bib @@ -2,7 +2,7 @@ author = "Michael A. Bender and Martin Farach-Colton", title = "The {LCA} Problem Revisited", booktitle = "Latin American Theoretical {INformatics}", - pages = "88-94", + pages = "88--94", year = "2000", url = "citeseer.ist.psu.edu/bender00lca.html" } @@ -10,7 +10,7 @@ author = "Greg N. Frederickson", 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", + pages = "632--641", year = "1991", url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" } @@ -28,7 +28,7 @@ address = {New York, NY, USA}, } -@inproceedings { fw90trans, +@inproceedings { fw:transdich, author = "M. Fredman and D. E. Willard", title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}", booktitle = "{Proceedings of FOCS'90}", @@ -36,7 +36,7 @@ year = "1990" } -@article{boas77, +@article{ boas:vebt, author = {Peter van Emde Boas}, title = {Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space.}, @@ -48,20 +48,8 @@ bibsource = {DBLP, http://dblp.uni-trier.de} } -@inproceedings{thorup03ac0, - author = {Mikkel Thorup}, - title = {On AC0 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{ benamram95what, - author = "Ben-Amram", +@article{ benamram:pm, + author = "Ben-Amram, Amir M.", title = "What is a ``Pointer Machine''?", journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)", volume = "26", @@ -105,10 +93,14 @@ year = "2001" } -@unpublished { nesetril:minors, +@incollection { nesetril:minors, author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez", - title = "{Colorings and Homomorphism of Minor Closed Classes}", - note = "To appear in {\it Pollack-Goodman Festschrift,} Springer Verlag, 2002." + title = "{Colorings and Homomorphisms of Minor Closed Classes}", + booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift", + editor = "B. Aronov and S. Basu and J. Pach and M. Sharir", + year = "2003", + pages = "651--664", + publisher = "Springer Verlag" } @article { boruvka:ojistem, @@ -123,7 +115,7 @@ @article { boruvka:networks, author = "Otakar Bor{\accent23u}vka", - title = "{P\v{r}\'\i{}sp\v{e}vek k~\v{r}e\v{s}en\'\i{} ot\'azky ekonomick\'e stavby elektrovodn\'\i{}ch s\'\i{}t\'\i{} (Contribution to the solution of a problem of economical construction of electric networks)}", + title = "{P\v{r}\'\i{}sp\v{e}vek k~\v{r}e\v{s}en\'\i{} ot\'azky ekonomick\'e stavby elektrovodn\'y{}ch s\'\i{}t\'\i{} (Contribution to the solution of a problem of economical construction of electric networks)}", journal = "Elektronick\'y obzor", volume = "15", year = "1926", @@ -161,7 +153,7 @@ @techreport { pettie:ackermann, author = "Seth Pettie", - title = "{Finding minimum spanning trees in $O(m\alpha(m,n))$ time}", + title = "{Finding minimum spanning trees in $\O(m\alpha(m,n))$ time}", institution = "Univ. of Texas at Austin", year = "1999", number = "TR99-23", @@ -177,6 +169,13 @@ pages = "49--60" } +@article { pettie:alpha, + title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}}, + author={Pettie, S.}, + year={1999}, + publisher={University of Texas at Austin Austin, TX, USA} +} + @article { karger:randomized, author = "D. R. Karger and P. N. Klein and R. E. Tarjan", title = "{Linear expected-time algorithms for connectivity problems}", @@ -204,6 +203,18 @@ year = "2004" } +@inproceedings{ mm:rank, + author = "Martin Mare\v{s} and Milan Straka", + title = "Linear-Time Ranking of Permutations", + booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium", + location = "Eilat, Israel, October 8--10, 2007", + volume = "4698", + series = "Lecture Notes in Computer Science", + pages = "187--193", + publisher = "Springer", + year = "2007", +} + @article{ ft:fibonacci, author = {Michael L. Fredman and Robert Endre Tarjan}, title = {Fibonacci heaps and their uses in improved network optimization algorithms}, @@ -237,6 +248,15 @@ year = "1995", url = "citeseer.ist.psu.edu/king95simpler.html" } +@article{ king:verifytwo, + title={{A Simpler Minimum Spanning Tree Verification Algorithm}}, + author={King, Valerie}, + journal={Algorithmica}, + volume={18}, + pages={263--270}, + year={1997} +} + @book { schrijver, author = "Alexander Schrijver", title = "{Combinatorial Optimization --- Polyhedra and Efficiency}", @@ -246,7 +266,7 @@ publisher = "Springer Verlag" } -@inproceedings{ thorup:ac0, +@inproceedings{ thorup:aczero, 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}, @@ -273,16 +293,7 @@ title={{Graph Theory}}, author={Diestel, R.}, year={2005}, - publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K} -} - -@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} + publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.} } @article{ graham:msthistory, @@ -325,19 +336,559 @@ } @article{ choquet:mst, - title={{Etude de certains r{\'e}seaux de routes (in French)}}, + title={{Etude de certains r{\'e}seaux de routes}}, author={Choquet, Gustave}, journal={Comptes-rendus de l'Académie des Sciences}, volume={206}, pages={310}, - year={1938} + year={1938}, + note={French} } @incollection { sollin:mst, - title={{Le trace de canalisation (in French)}}, + title={{Le trace de canalisation}}, author={Sollin, M.}, booktitle={Programming, Games, and Transportation Networks}, editor={Berge, C. and Ghouilla-Houri, A.}, publisher={Wiley, New York}, - year={1965} + year={1965}, + note={French} +} + +@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} +} + +@inproceedings{ takaoka:twothree, + title={{Theory of 2-3 Heaps}}, + author={Takaoka, T. and Christchurch, N. Z.}, + booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON'99}, + location={Tokyo, Japan}, + year={1999}, + pages={41--50}, + publisher={Springer}, + series={{Lecture Notes in Computer Science}}, + volume={1627} +} + +@inproceedings{ takaoka:trinomial, + title={{Theory of Trinomial Heaps}}, + author={Takaoka, Tadao}, + booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000}, + location={Sydney, Australia}, + year={2000}, + pages={362--372}, + publisher={Springer}, + series={{Lecture Notes in Computer Science}}, + volume={1858} +} + +@book{ clrs, + title={{Introduction to Algorithms}}, + author={Leiserson, C.E. and Rivest, R.L. and Cormen, T.H. and Stein, C.}, + year={2001}, + publisher={McGraw-Hill} +} + +@inproceedings{ pettie:onlineverify, + author = "S. Pettie", + title = "An inverse-{A}ckermann style lower bound for the online minimum spanning + tree verification problem", + booktitle = "Proc. 43rd Annual Symp. on the Foundations of Computer Science, Vancouver, Canada", + year = "2002", + url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html" +} + +@article{ dixon:verify, + author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan", + title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time", + journal = "SIAM J. Comput.", + volume = "21", + number = "6", + pages = "1184-1192", + year = "1992", + url = "citeseer.ist.psu.edu/dixon92verification.html" +} + +inproceedings{ pettie:minirand, + author = {Seth Pettie and Vijaya Ramachandran}, + title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms}, + booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms}, + year = {2002}, + isbn = {0-89871-513-X}, + pages = {713--722}, + location = {San Francisco, California}, + publisher = {Society for Industrial and Applied Mathematics}, + address = {Philadelphia, PA, USA} +} + +@article{ buchsbaum:verify, + title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}}, + author={Buchsbaum, A.L. and Kaplan, H. and Rogers, A. and Westbrook, J.R.}, + journal={Proceedings of the thirtieth annual ACM Symposium on Theory of Computing}, + pages={279--288}, + year={1998}, + publisher={ACM Press New York, NY, USA} +} + +@article{ bacala:parametric, + title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}}, + author={Fern{\'a}ndez-Baca, D. and Slutzki, G.}, + journal={Theoretical Computer Science}, + volume={181}, + number={1}, + pages={57--74}, + year={1997}, + publisher={Elsevier} +} + +@inproceedings{ katriel:cycle, + author = "I. Katriel and P. Sanders and J. Tr{\"a}ff", + title = "A practical minimum spanning tree algorithm using the cycle property", + booktitle = "11th European Symposium on Algorithms (ESA)", + number = "2832", + series = "LNCS", + pages = "679--690", + publisher = "Springer", + year = "2003", + url = "citeseer.ist.psu.edu/katriel03practical.html" +} + +@article{ alstrup:nca, + title={{Nearest common ancestors: a survey and a new distributed algorithm}}, + author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.}, + journal={Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures}, + pages={258--264}, + year={2002}, + publisher={ACM Press New York, NY, USA} +} + +@article{ gabow:mst, + title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}}, + author={Gabow, H.N. and Galil, Z. and Spencer, T. and Tarjan, R.E.}, + journal={Combinatorica}, + volume={6}, + number={2}, + pages={109--122}, + year={1986}, + publisher={Springer} +} + +@Unpublished{ eisner:tutorial, + author = {Jason Eisner}, + title = {State-of-the-Art Algorithms for Minimum Spanning + Trees: A Tutorial Discussion}, + note = {Manuscript available online (78 pages), University of Pennsylvania}, + year = 1997, + url = {http://cs.jhu.edu/~jason/papers/#ms97}, +} + +@article{ aho:lca, + title={{On finding lowest common ancestors in trees.}}, + author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.}, + journal={SIAM Journal on Computing}, + volume={5}, + pages={115--132}, + year={1976} +} + +@book{ knuth:fundalg, + author = {Donald E. Knuth}, + title = {The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms}, + year = {1997}, + isbn = {0-201-89683-4}, + publisher = {Addison Wesley Longman Publishing Co., Inc.}, + address = {Redwood City, CA, USA}, +} + +@book{ knuth:seminalg, + author = {Donald E. Knuth}, + title = {The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical algorithms}, + year = {1997}, + isbn = {978-0-201-89684-8}, + publisher = {Addison Wesley Longman Publishing Co., Inc.}, + address = {Redwood City, CA, USA}, +} + +@book{ knuth:sas, + author = {Donald E. Knuth}, + title = {{The Art of Computer Programming, Volume 3 (2nd ed.): Sorting and Searching}}, + year = {1998}, + isbn = {978-0-201-89685-5}, + publisher = {Addison Wesley Longman Publishing Co., Inc.}, + address = {Redwood City, CA, USA}, +} + +@inproceedings{ hagerup:wordram, + author = {Torben Hagerup}, + title = {{Sorting and Searching on the Word RAM}}, + booktitle = {STACS '98: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science}, + year = {1998}, + isbn = {3-540-64230-7}, + pages = {366--398}, + publisher = {Springer-Verlag}, + address = {London, UK}, +} + +@inproceedings{ cook:ram, + author = {Stephen A. Cook and Robert A. Reckhow}, + title = {Time-bounded random access machines}, + booktitle = {STOC '72: Proceedings of the fourth annual ACM Symposium on Theory of Computing}, + year = {1972}, + pages = {73--80}, + location = {Denver, Colorado, United States}, + doi = {http://doi.acm.org/10.1145/800152.804898}, + publisher = {ACM}, + address = {New York, NY, USA}, +} + +@book{ okasaki:funcds, + author = {Chris Okasaki}, + title = {Purely Functional Data Structures}, + year = {1999}, + publisher = {Cambridge University Press} +} + +@book { intel:pentium, + author = {{Intel Corp.}}, + title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference}, + year = {2007}, + publisher = {Intel Corp.}, + xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm} +} + +@article{ hagerup:dd, + title={{Deterministic Dictionaries}}, + author={Hagerup, T. and Miltersen, P.B. and Pagh, R.}, + journal={J. Algorithms}, + volume={41}, + number={1}, + pages={69--85}, + year={2001} +} + +@article{ fredman:sst, + title={{Storing a Sparse Table with $\O(1)$ Worst Case Access Time}}, + author={Fredman, M.L. and Koml{\'o}s, J. and Szemer{\'e}di, E.}, + journal={Journal of the ACM (JACM)}, + volume={31}, + number={3}, + pages={538--544}, + year={1984}, + publisher={ACM Press New York, NY, USA} +} + +@book{ motwani:randalg, + title={{Randomized Algorithms}}, + author={Motwani, R. and Raghavan, P.}, + year={1995}, + publisher={Cambridge University Press} +} + +@article{ fw:fusion, + title={{Surpassing the information theoretic bound with fusion trees}}, + author={Fredman, M.L. and Willard, D.E.}, + journal={Journal of Computer and System Sciences}, + volume={47}, + number={3}, + pages={424--436}, + year={1993}, + publisher={Academic Press, Inc. Orlando, FL, USA} +} + +@article{ han:detsort, + title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}}, + author={Han, Y.}, + journal={Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing}, + pages={602--608}, + year={2002}, + publisher={ACM Press New York, NY, USA} +} + +@article{ hanthor:randsort, + title={{Integer Sorting in $\O(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{ ito:newrap, + title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}}, + author={Ito, M. and Takagi, N. and Yajima, S.}, + journal={Proc. 12th IEEE Symp. Computer Arithmetic}, + pages={2--9}, + year={1995} +} + +@article{ brodnik:lsb, + title={{Computation of the least significant set bit}}, + author={Brodnik, A.}, + journal={Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia}, + year={1993} +} + +@article{ turan:succinct, + title={{Succinct representation of graphs.}}, + author={Tur\'an, G.}, + journal={Discrete Applied Mathematics}, + volume={8}, + number={3}, + pages={289--294}, + year={1984} +} + +@book{ jones:haskell, + title={{Haskell 98 Language and Libraries: The Revised Report}}, + author={Jones, P. and Simon, L.}, + year={2003}, + publisher={Cambridge University Press} +} + +@article{ mader:dens, + title={{Homomorphieeigenschaften und mittlere Kantendichte von Graphen}}, + author={Mader, W.}, + journal={Mathematische Annalen}, + volume={174}, + number={4}, + pages={265--268}, + year={1967}, + publisher={Springer}, + note={German} +} + +@inproceedings{ gustedt:parallel, + author = "Jens Gustedt", + title = "Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel", + booktitle = "Symposium on Theoretical Aspects of Computer Science", + pages = "421-431", + year = "1998", + url = "citeseer.ist.psu.edu/223918.html" +} + +@article{ myrvold:rank, + title={{Ranking and unranking permutations in linear time}}, + author={Myrvold, W.J. and Ruskey, F.}, + journal={Information Processing Letters}, + volume={79}, + number={6}, + pages={281--284}, + year={2001} +} + +@inproceedings{ critani:rau, + title={{Ranking and unranking permutations with applications}}, + author={Critani, F. and Dall'Aglio, M. and Di Biase, G.}, + booktitle={Innovation in Mathematics: Proceedings of Second International Mathematica Symposium}, + pages = "99-106", + year = "1997" +} + +@article{ ruskey:ham, + title={{The Hamiltonicity of directed-Cayley graphs (or: A tale of backtracking)}}, + author={Ruskey, F. and Jiang, M. and Weston, A.}, + journal={Discrete Appl. Math}, + volume={57}, + pages={75--83}, + year={1995} +} + +@article{ ruskey:hce, + title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn}}, + author={Ruskey, F. and Savage, C.D.}, + journal={SIAM Journal on Discrete Mathematics}, + volume={6}, + number={1}, + pages={152--166}, + year={1993} +} + +@article{ liehe:raulow, + title={{Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis}}, + author={Liebehenschel, J.}, + journal={Journal of Automata, Languages and Combinatorics}, + volume={2}, + number={4}, + pages={227--268}, + year={1997} +} + +@book{ reingold:catp, + title={{Combinatorial Algorithms: Theory and Practice}}, + author={Reingold, E.M.}, + year={1977}, + publisher={Prentice Hall College Div} +} + +@inproceedings{ dietz:oal, + author = {Paul F. Dietz}, + title = {Optimal Algorithms for List Indexing and Subset Rank}, + booktitle = {WADS '89: Proceedings of the Workshop on Algorithms and Data Structures}, + year = {1989}, + isbn = {3-540-51542-9}, + pages = {39--46}, + publisher = {Springer-Verlag}, + address = {London, UK}, +} + +@book { ss:fifteen, + title={{The 15 Puzzle Book}}, + author={Slocum, J. and Sonneveld D.}, + year={2006}, + publisher={The Slocum Puzzle Foundation, Beverly Hills, CA, USA} +} + +@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}, + publisher={Academic Press, Inc. Orlando, FL, USA} +} + +@book{ matnes:idm, + title={{Invitation to Discrete Mathematics}}, + author={Matou{\v{s}}ek, J. and Ne{\v{s}}et{\v{r}}il, J.}, + year={1998}, + publisher={Oxford University Press} +} + +@article{ stanley:econe, + title={{Enumerative combinatorics. Vol. 1}}, + author={Stanley, R.P.}, + journal={Cambridge Studies in Advanced Mathematics}, + volume={49}, + year={1997} +} + +@article{ kaplansky:rooks, + title={{The problem of the rooks and its applications}}, + author={Kaplansky, I. and Riordan, J.}, + journal={Duke Math. J}, + volume={13}, + number={2}, + pages={259--268}, + year={1946} +} + +@article{ dinic:flow, + author = {E. A. Dinic}, + title = {Algorithm for solution of a problem of maximum flow in networks with power estimation}, + journal = {Soviet Math. Dokl.}, + volume = {11}, + year = {1970}, + pages = {1277--1280} +} + +@article{ even:dinic, + author = {Shimon Even and Robert Endre Tarjan}, + title = {Network Flow and Testing Graph Connectivity}, + publisher = {SIAM}, + year = {1975}, + journal = {SIAM Journal on Computing}, + volume = {4}, + number = {4}, + pages = {507--518}, + url = {http://link.aip.org/link/?SMJ/4/507/1}, + doi = {10.1137/0204043} +} + +@article{ valiant:permanent, + title={{The complexity of computing the permanent}}, + author={Valiant, L. G.}, + journal={Theoretical Computer Science}, + volume={8}, + number={2}, + pages={189--201}, + year={1979} +} + +@article{ jerrum:permanent, + title={{A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries}}, + author={Jerrum, M. and Sinclair, A. and Vigoda, E.}, + journal={Journal of the ACM}, + volume={51}, + number={4}, + pages={671--697}, + year={2004} +} + +@article{ kasteleyn:crystals, + title={{Graph theory and crystal physics}}, + author={Kasteleyn, P. W.}, + journal={Graph Theory and Theoretical Physics}, + publisher={Academic Press, London}, + pages={43--110}, + year={1967} +} + +@article{ yuster:matching, + title={{Maximum matching in graphs with an excluded minor}}, + author={Yuster, R. and Zwick, U.}, + journal={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms}, + pages={108--117}, + year={2007}, + publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA} +} + +@article{ mucha:matching, + title={{Maximum Matchings in Planar Graphs via Gaussian Elimination}}, + author={Mucha, M. and Sankowski, P.}, + journal={Algorithmica}, + volume={45}, + number={1}, + pages={3--20}, + year={2006}, + publisher={Springer} +} + +@article {lovasz:minors, + title={{Graph Minor Theory}}, + author={Lov\'asz, L.}, + journal={Bulletin of the American Mathematical Society}, + volume={43}, + number={1}, + pages={75--86}, + year={2005} +} + +@article{ andersson:fusion, + title={{Fusion trees can be implemented with AC0 instructions only}}, + author={Andersson, A. and Miltersen, P.B. and Thorup, M.}, + journal={Theoretical Computer Science}, + volume={215}, + number={1-2}, + pages={337--344}, + year={1999}, + publisher={Elsevier} +} + +@article{ thorup:rampq, + title={{On RAM priority queues}}, + author={THORUP, M.}, + journal={SIAM journal on computing(Print)}, + volume={30}, + number={1}, + pages={86--109}, + year={2001}, + publisher={Society for Industrial and Applied Mathematics} +} + +@article{ thorup:pqsssp, + 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} }