X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=biblio.bib;h=33115567ebcc4fcd2e55f5421334eed8b6fb8906;hb=2673d7b09e7049aa35f3f81b6e7b395c934bdfbd;hp=01aca865a65804cccbf076118ffc0920879d85eb;hpb=0e783e3fc00288b976fc0277e8948f3bc90cab98;p=saga.git

diff --git a/biblio.bib b/biblio.bib
index 01aca86..3311556 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -14,7 +14,7 @@
     year = "1991",
     url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" }
 
-@article{ tarjan:setunion,
+@article{ tarjan:wcsetunion,
  author = {Robert E. Tarjan and Jan van Leeuwen},
  title = {Worst-case Analysis of Set Union Algorithms},
  journal = {J. ACM},
@@ -28,6 +28,17 @@
  address = {New York, NY, USA},
 }
 
+@article{ tarjan:setunion,
+  title={{Efficiency of a Good But Not Linear Set Union Algorithm}},
+  author={Tarjan, R.E.},
+  journal={Journal of the ACM},
+  volume={22},
+  number={2},
+  pages={215--225},
+  year={1975},
+  publisher={ACM Press New York, NY, USA}
+}
+
 @inproceedings { fw:transdich,
    author = "M. Fredman and D. E. Willard",
    title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}",
@@ -75,6 +86,15 @@
     year = "2000"
 }
 
+@article{ chazelle:almostacker,
+  title={{A faster deterministic algorithm for minimum spanning trees}},
+  author={Chazelle, B.},
+  journal={Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS'97)},
+  pages={22},
+  year={1997},
+  publisher={IEEE Computer Society Washington, DC, USA}
+}
+
 @article{ nesetril:history,
     author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
     title = "{Some remarks on the history of MST-problem}",
@@ -110,7 +130,7 @@
     volume = "III",
     year = "1926",
     pages = "37--58",
-    note = "Czech with German summary"
+    note = "In Czech with German summary"
 }
 
 @article { boruvka:networks,
@@ -120,7 +140,7 @@
     volume = "15",
     year = "1926",
     pages = "153--154",
-    note = "Czech"
+    note = "In Czech"
 }
 
 @article { jarnik:ojistem,
@@ -130,7 +150,7 @@
     volume = "VI",
     year = "1930",
     pages = "57--63",
-    note = "Czech"
+    note = "In Czech"
 }
 
 @book { tarjan:dsna,
@@ -160,7 +180,17 @@
     type = "Tech Report"
 }
 
-@inproceedings { pettie:optimal,
+@article{ pettie:optimal,
+ author = {Seth Pettie and Vijaya Ramachandran},
+ title= {An optimal minimum spanning tree algorithm},
+ journal = {Journal of the {ACM}},
+ volume = {49},
+ number = {1},
+ year = {2002},
+ pages = {16--34},
+}
+
+@inproceedings { pettie:optimal-conf,
    author = "Seth Pettie and Vijaya Ramachandran",
    title = "{An Optimal Minimum Spanning Tree Algorithm}",
    booktitle = "{Proceedings of ICALP'2000}",
@@ -362,7 +392,7 @@
   volume={206},
   pages={310},
   year={1938},
-  note={French}
+  note={In French}
 }
 
 @incollection { sollin:mst,
@@ -372,7 +402,7 @@
   editor={Berge, C. and Ghouilla-Houri, A.},
   publisher={Wiley, New York},
   year={1965},
-  note={French}
+  note={In French}
 }
 
 @article{ boyer:cutting,
@@ -416,7 +446,18 @@
   publisher={McGraw-Hill}
 }
 
-@inproceedings{ pettie:onlineverify,
+@article{ pettie:onlineverify,
+ author       = {Seth Pettie},
+ title        = {An Inverse-{A}ckermann Type Lower Bound for Online
+                 Minimum Spanning Tree Verification},
+ journal      = {Combinatorica},
+ volume       = {26},
+ number       = {2},
+ pages        = {207--230},
+ year         = {2006},
+}
+
+@inproceedings{ pettie:onlineverify-conf,
   author = "S. Pettie",
   title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
     tree verification problem",
@@ -436,7 +477,7 @@
     url = "citeseer.ist.psu.edu/dixon92verification.html"
 }
 
-inproceedings{ pettie:minirand,
+@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},
@@ -681,7 +722,7 @@ inproceedings{ pettie:minirand,
   pages={265--268},
   year={1967},
   publisher={Springer},
-  note={German}
+  note={In German}
 }
 
 @inproceedings{ gustedt:parallel,
@@ -1109,3 +1150,422 @@ inproceedings{ pettie:minirand,
   year={1952},
   publisher={JSTOR}
 }
+
+@article{ pettie:parallel,
+ author       = {Seth Pettie and Vijaya Ramachandran},
+ title        = {A randomized time-work optimal parallel algorithm for
+                 finding a minimum spanning forest},
+ journal      = {SIAM J. Comput.},
+ volume       = {31},
+ number       = {6},
+ year         = {2002},
+ pages        = {1879--1895},
+}
+
+@article{ chazelle:softheap,
+ author = {Bernard Chazelle},
+ title = {The soft heap: an approximate priority queue with optimal error rate},
+ journal = {J. ACM},
+ volume = {47},
+ number = {6},
+ year = {2000},
+ issn = {0004-5411},
+ pages = {1012--1027},
+ doi = {http://doi.acm.org/10.1145/355541.355554},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
+
+@article{ propp:randommst,
+ author = {James Gary Propp and David Bruce Wilson},
+ title = {How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph},
+ journal = {J. Algorithms},
+ volume = {27},
+ number = {2},
+ year = {1998},
+ issn = {0196-6774},
+ pages = {170--217},
+ doi = {http://dx.doi.org/10.1006/jagm.1997.0917},
+ publisher = {Academic Press, Inc.},
+ address = {Duluth, MN, USA},
+}
+
+@article{ vuillemin:binheap,
+  title={{A Data Structure for Manipulating Priority Queues}},
+  author={Vuillemin, Jean},
+  journal={Communications of the ACM},
+  volume = 21,
+  number = 4,
+  pages={309--315},
+  year={1978}
+}
+
+@article{ hoare:qsort,
+  title={{Quicksort}},
+  author={Hoare, Charles Anthony Richard},
+  journal={The Computer Journal},
+  volume={5},
+  number={1},
+  pages={10--16},
+  year={1962},
+  publisher={British Computer Society}
+}
+
+@article{ blum:selection,
+  title={{Time bounds for selection}},
+  author={Blum, M. and Floyd, R.W. and Pratt, V. and Rivest, R.L. and Tarjan, R.E.},
+  journal={Journal of Computer and System Sciences},
+  volume={7},
+  number={4},
+  pages={448--461},
+  year={1973}
+}
+
+@article{ hoare:qselect,
+ author = {Hoare, Charles Anthony Richard},
+ title = {Algorithm 65: find},
+ journal = {Communications of the ACM},
+ volume = {4},
+ number = {7},
+ year = {1961},
+ issn = {0001-0782},
+ pages = {321--322},
+ doi = {http://doi.acm.org/10.1145/366622.366647},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
+
+@article{ dinitz:treeiso,
+  title={{On an algorithm of Zemlyachenko for subtree isomorphism}},
+  author={Dinitz, Y. and Itai, A. and Rodeh, M.},
+  journal={Information Processing Letters},
+  volume={70},
+  number={3},
+  pages={141--146},
+  year={1999},
+  publisher={Elsevier}
+}
+
+@inproceedings{ zemlay:treeiso,
+  title={{Determining tree isomorphism}},
+  author={Zemlayachenko, V. N.},
+  booktitle={{Voprosy Kibernetiki, Proceedings of the Seminar on Combinatorial Mathematics}},
+  location={Moscow 1971},
+  publisher={{Scientific Council of the Complex Problem ``Kibernetika'', Akad. Nauk SSSR}},
+  year={1973},
+  pages={54--60},
+  note={In Russian},
+}
+
+@article{ alstrup:marked,
+  title={{Marked ancestor problems}},
+  author={Alstrup, S. and Husfeldt, T. and Rauhe, T.},
+  journal={Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on},
+  pages={534--543},
+  year={1998}
+}
+
+@article{ arvind:isomorph,
+  title={{Graph isomorphism is in SPP}},
+  author={Arvind, V. and Kurur, P. P.},
+  journal={Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on},
+  pages={743--750},
+  year={2002}
+}
+
+@article{ ackermann:function,
+  title={{Zum Hilbertschen Aufbau der reellen Zahlen}},
+  author={Ackermann, W.},
+  journal={Mathematische Annalen},
+  volume={99},
+  number={1},
+  pages={118--133},
+  year={1928},
+  publisher={Springer},
+  notes={In German}
+}
+
+@article{ klazar:gdss,
+  title={{Generalized Davenport--Schinzel Sequences: Results, problems, and applications}},
+  author={Klazar, M.},
+  journal={INTEGERS: The Electronic Journal of Combinatorial Number Theory},
+  volume={2},
+  number={A11},
+  pages={2},
+  year={2002}
+}
+
+@inproceedings{ fredman:cellprobe,
+  author = {M. Fredman and M. Saks},
+  title = {The cell probe complexity of dynamic data structures},
+  booktitle = {STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing},
+  year = {1989},
+  isbn = {0-89791-307-8},
+  pages = {345--354},
+  location = {Seattle, Washington, United States},
+  doi = {http://doi.acm.org/10.1145/73007.73040},
+  publisher = {ACM},
+  address = {New York, NY, USA},
+}
+
+@article{ henzinger:randdyn,
+  title={{Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation}},
+  author={Henzinger, M.R. and King, V.},
+  journal={Journal of the ACM},
+  volume={46},
+  number={4},
+  pages={502--516},
+  year={1999}
+}
+
+@article{ holm:polylog,
+  title={{Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity}},
+  author={Holm, J. and de Lichtenberg, K. and Thorup, M.},
+  journal={Journal of the ACM (JACM)},
+  volume={48},
+  number={4},
+  pages={723--760},
+  year={2001},
+  publisher={ACM Press New York, NY, USA}
+}
+
+@article{ frederickson:dynamic,
+  title={{Data structures for on-line updating of minimum spanning trees, with applications}},
+  author={Frederickson, G. N.},
+  journal={SIAM Journal of Computing},
+  volume={14},
+  pages={781--798},
+  year={1985}
+}
+
+@article{ eppstein:sparsify,
+  title={{Sparsification --- a technique for speeding up dynamic graph algorithms}},
+  author={Eppstein, D. and Galil, Z. and Italiano, G.F. and Nissenzweig, A.},
+  journal={Journal of the ACM},
+  volume={44},
+  number={5},
+  pages={669--696},
+  year={1997},
+  publisher={ACM Press New York, NY, USA}
+}
+
+@article{ henzinger:mst,
+  title={{Maintaining minimum spanning trees in dynamic graphs}},
+  author={Henzinger, M.R. and King, V.},
+  journal={Proceedings of the 24th International Colloquium on Automata, Languages and Programming},
+  pages={594--604},
+  year={1997},
+  publisher={Springer}
+}
+
+@mastersthesis { mares:dga,
+  title={{Dynamick\'e grafov\'e algoritmy}},
+  author={Martin Mare\v{s}},
+  school={Charles University in Prague, Faculty of Math and Physics},
+  year={2000},
+  notes={In Czech}
+}
+
+@techreport{ henzinger:twoec,
+  title = {Fully dynamic 2-edge-connectivity algorithm in polylogarithmic time per operation},
+  author = {Monika Rauch Henzinger and Valerie King},
+  type = {Technical note},
+  institution = {Digital Equipment Corp., Systems Research Ctr.},
+  address = {130 Lytton Rd., Palo Alto, CA, 94301, USA},
+  number = {1997-004},
+  month = {12 Jun},
+  year = {1997},
+  url = {http://gatekeeper.dec.com/pub/DEC/SRC/technical-notes/abstracts/src-tn-1997-004.html}
+}
+
+@book{ overmars:ds,
+  author = {Mark H. Overmars},
+  title = {Design of Dynamic Data Structures},
+  year = {1987},
+  isbn = {038712330X},
+  publisher = {Springer-Verlag New York, Inc.},
+  address = {Secaucus, NJ, USA},
+  series={{Lecture Notes in Computer Science}},
+  volume={156}
+}
+
+@article{ eppstein:ksmallest,
+  title={{Finding the $k$~Smallest Spanning Trees}},
+  author={Eppstein, D.},
+  journal={BIT},
+  volume={32},
+  number={2},
+  pages={237--248},
+  year={1992},
+  publisher={Springer}
+}
+
+@article{ katoh:ksmallest,
+  title={{An Algorithm for Finding\$ K\$ Minimum Spanning Trees}},
+  author={Katoh, N. and Ibaraki, T. and Mine, H.},
+  journal={SIAM Journal on Computing},
+  volume={10},
+  pages={247},
+  year={1981},
+  publisher={SIAM}
+}
+
+@inproceedings{ thorup:nearopt,
+ author = {Mikkel Thorup},
+ title = {Near-optimal fully-dynamic graph connectivity},
+ booktitle = {STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computing},
+ year = {2000},
+ isbn = {1-58113-184-4},
+ pages = {343--350},
+ location = {Portland, Oregon, United States},
+ doi = {http://doi.acm.org/10.1145/335305.335345},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
+
+@article{ henzinger:lowerbounds,
+  title={{Lower Bounds for Fully Dynamic Connectivity Problems in Graphs}},
+  author={Henzinger, M. R. and Fredman, M. L.},
+  journal={Algorithmica},
+  volume={22},
+  number={3},
+  pages={351--362},
+  year={1998},
+  publisher={Springer}
+}
+
+@article{ thorup:usssp,
+  title={{Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time}},
+  author={Thorup, Mikkel},
+  journal={Journal of the ACM},
+  volume={46},
+  number={3},
+  pages={362--394},
+  year={1999}
+}
+
+@article{ thorup:sssp,
+  author = {Mikkel Thorup},
+  title = {Integer priority queues with decrease key in constant time and the single source shortest paths problem},
+  journal = {Journal of Computer and System Sciences},
+  volume = {69},
+  number = {3},
+  year = {2004},
+  issn = {0022-0000},
+  pages = {330--353},
+  doi = {http://dx.doi.org/10.1016/j.jcss.2004.04.003},
+  publisher = {Academic Press, Inc.},
+  address = {Orlando, FL, USA},
+}
+
+@inproceedings{ hagerup:sssp,
+  author = {Torben Hagerup},
+  title = {Improved Shortest Paths on the Word RAM},
+  booktitle = {ICALP '00: Proceedings of the 27th International Colloquium on Automata, Languages and Programming},
+  year = {2000},
+  isbn = {3-540-67715-1},
+  pages = {61--72},
+  publisher = {Springer-Verlag},
+  address = {London, UK},
+}
+
+@techreport { hakmem,
+    author = "Beeler, Michael and Gosper, R. William and Schroeppel, Rich",
+    title = "{HAKMEM}",
+    institution = "Massachusetts Institute of Technology",
+    year = "1972",
+    number = "239",
+    type = "Memo"
+}
+
+@book{ oxley:matroids,
+  title={{Matroid Theory}},
+  author={Oxley, J.G.},
+  year={1992},
+  publisher={Oxford University Press}
+}
+
+@article{ katoh:kmin,
+  author = {N. Katoh and T. Ibaraki and H. Mine},
+  title = {An Algorithm for Finding $K$ Minimum Spanning Trees},
+  publisher = {SIAM},
+  year = {1981},
+  journal = {SIAM Journal on Computing},
+  volume = {10},
+  number = {2},
+  pages = {247--255},
+}
+
+@article{ chong:parallel,
+  author = {Ka Wong Chong and Yijie Han and Tak Wah Lam},
+  title = {Concurrent threads and optimal parallel minimum spanning trees algorithm},
+  journal = {Journal of the ACM},
+  volume = {48},
+  number = {2},
+  year = {2001},
+  issn = {0004-5411},
+  pages = {297--323},
+  doi = {http://doi.acm.org/10.1145/375827.375847},
+  publisher = {ACM},
+  address = {New York, NY, USA},
+}
+
+@article{ moret:expmst,
+  title={{An Empirical Assessment of Algorithms for Constructing a Minimum Spanning Tree}},
+  author={Moret, B. M. E. and Shapiro, H. D.},
+  journal={Computational Support for Discrete Mathematics: DIMACS Workshop, March 12-14, 1992},
+  year={1994},
+  publisher={American Mathematical Society}
+}
+
+@article{ fredman:pairingheap,
+  title={{The pairing heap: A new form of self-adjusting heap}},
+  author={Fredman, M.L. and Sedgewick, R. and Sleator, D.D. and Tarjan, R.E.},
+  journal={Algorithmica},
+  volume={1},
+  number={1},
+  pages={111--129},
+  year={1986},
+  publisher={Springer}
+}
+
+@article{ pettie:pairing,
+  author = {Seth Pettie},
+  title = {Towards a Final Analysis of Pairing Heaps},
+  journal = {focs},
+  volume = {00},
+  year = {2005},
+  isbn = {0-7695-2468-0},
+  pages = {174-183},
+  doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.75},
+  publisher = {IEEE Computer Society},
+  address = {Los Alamitos, CA, USA},
+}
+
+@book{ jaja:parallel,
+  title={{An introduction to parallel algorithms}},
+  author={J{\'a}J{\'a}, J.},
+  year={1992},
+  publisher={Addison Wesley Longman Publishing Co., Inc. Redwood City, CA, USA}
+}
+
+@techreport { mm:ga,
+  author = "Martin Mare\v{s}",
+  title = "{Krajinou grafov\'ych algoritm\accent23u}",
+  institution = "Institut Teoretick\'e Informatiky",
+  address = "Praha, Czech Republic",
+  year = "2007",
+  number = "2007--330",
+  type = "ITI series",
+  note = {In Czech},
+}
+
+@book { horak:mofivefour,
+  author = {Hor\'ak, Karel and Mare\v{s}, Martin and Novotn\'y, Peter and \v{S}im\v{s}a, Jarom\'\i{}r and \v{S}vr\v{c}ek, Jaroslav and T\"opfer, Pavel and Zhouf, Jaroslav},
+  title = {54.~ro\v{c}n\'\i{}k matematick\'e olympi\'ady na st\v{r}edn\'\i{}ch \v{s}kol\'ach},
+  publisher = {Jednota \v{c}esk\'ych matematik\accent23u a fyzik\accent23u},
+  address = {Praha},
+  year = {2007},
+  note = {In Czech},
+  isbn = {80-7015-109-9},
+}