X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=biblio.bib;h=e74fa0903e9353d2d8125030a23776f5cf998715;hb=2f5c7308e7d6e11493e8ee68bf52dad2d4c1bda3;hp=e2ea71b7a6a1537526e94cd53fdd922e5172abfd;hpb=e0783236c7c0618f4a3ad1f8e584423cfbb085fa;p=saga.git diff --git a/biblio.bib b/biblio.bib index e2ea71b..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,18 +48,6 @@ bibsource = {DBLP, http://dblp.uni-trier.de} } -@inproceedings{ thorup:aczero, - 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{ benamram:pm, author = "Ben-Amram, Amir M.", title = "What is a ``Pointer Machine''?", @@ -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} @@ -507,13 +497,22 @@ inproceedings{ pettie:minirand, @book{ knuth:fundalg, author = {Donald E. Knuth}, - title = {The art of computer programming, volume 1 (3rd ed.): fundamental algorithms}, + 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}}, @@ -528,7 +527,7 @@ inproceedings{ pettie:minirand, @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}, + booktitle = {STOC '72: Proceedings of the fourth annual ACM Symposium on Theory of Computing}, year = {1972}, pages = {73--80}, location = {Denver, Colorado, United States}, @@ -536,3 +535,107 @@ inproceedings{ pettie:minirand, 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} +}