X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=biblio.bib;h=304eb3cd27ad2dea9604638877eee3a7a3a17d7e;hb=e0ddb64ea79c2753f51ad2465c87ebfe1a75be4a;hp=e987e8c06776bc0048763de25ea5bc2391e7c522;hpb=882536cbac0bf156a9a1a2afed98af42c098d159;p=saga.git diff --git a/biblio.bib b/biblio.bib index e987e8c..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" } @@ -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", @@ -165,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", @@ -215,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}, @@ -266,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}, @@ -293,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, @@ -345,21 +336,23 @@ } @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, @@ -426,7 +419,7 @@ 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}, + booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms}, year = {2002}, isbn = {0-89871-513-X}, pages = {713--722}, @@ -438,7 +431,7 @@ inproceedings{ pettie:minirand, @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}, + journal={Proceedings of the thirtieth annual ACM Symposium on Theory of Computing}, pages={279--288}, year={1998}, publisher={ACM Press New York, NY, USA} @@ -458,7 +451,7 @@ inproceedings{ pettie:minirand, @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)", + booktitle = "11th European Symposium on Algorithms (ESA)", number = "2832", series = "LNCS", pages = "679--690", @@ -466,3 +459,436 @@ inproceedings{ pettie:minirand, 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} +}