X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=biblio.bib;h=e74fa0903e9353d2d8125030a23776f5cf998715;hb=2f5c7308e7d6e11493e8ee68bf52dad2d4c1bda3;hp=e987e8c06776bc0048763de25ea5bc2391e7c522;hpb=882536cbac0bf156a9a1a2afed98af42c098d159;p=saga.git diff --git a/biblio.bib b/biblio.bib index e987e8c..e74fa09 100644 --- a/biblio.bib +++ b/biblio.bib @@ -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", @@ -266,7 +254,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,13 +281,13 @@ title={{Graph Theory}}, author={Diestel, R.}, year={2005}, - publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K} + publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.} } @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}, + journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing}, pages={149--158}, year={2003}, publisher={ACM Press New York, NY, USA} @@ -345,21 +333,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 +416,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 +428,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} @@ -466,3 +456,186 @@ 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}, +} + +@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} +}