X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=biblio.bib;h=e74fa0903e9353d2d8125030a23776f5cf998715;hb=2f5c7308e7d6e11493e8ee68bf52dad2d4c1bda3;hp=446a32730768da4e320234ed5534f741e3484615;hpb=36a205a5091f23520c7cb9bd0cb05f7205cdee2b;p=saga.git

diff --git a/biblio.bib b/biblio.bib
index 446a327..e74fa09 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -14,7 +14,7 @@
     year = "1991",
     url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" }
 
-@article{ tarjan84setunion,
+@article{ tarjan:setunion,
  author = {Robert E. Tarjan and Jan van Leeuwen},
  title = {Worst-case Analysis of Set Union Algorithms},
  journal = {J. ACM},
@@ -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}",
@@ -237,6 +236,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 +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},
@@ -273,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}
@@ -325,19 +333,309 @@
 }
 
 @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},
+}
+
+@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}
 }