X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=biblio.bib;h=a2cbfa0aa827f460fa3de921740f6d441d01944c;hb=fd8aae91259d03ae549f483a5b658cd85b1f8626;hp=2e95fb0898a8fe884666e9a443dea469cb3496ed;hpb=ed224711cd723437d57856c74d2c57937eacc4e9;p=saga.git diff --git a/biblio.bib b/biblio.bib index 2e95fb0..a2cbfa0 100644 --- a/biblio.bib +++ b/biblio.bib @@ -1,20 +1,31 @@ -@inproceedings{ bender00lca, +@inproceedings{ bender:lca, 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" } -@inproceedings{ frederickson91ambivalent, +@article{ frederickson:ambivalent, + author = "Frederickson, Greg N.", + title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees", + journal={SIAM journal on computing}, + volume={26}, + number={2}, + pages={484--538}, + year={1997}, + publisher={Society for Industrial and Applied Mathematics} +} + +@inproceedings{ frederickson:ambifocs, 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" } -@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 +39,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 +97,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 +141,7 @@ volume = "III", year = "1926", pages = "37--58", - note = "Czech with German summary" + note = "In Czech with German summary" } @article { boruvka:networks, @@ -120,7 +151,7 @@ volume = "15", year = "1926", pages = "153--154", - note = "Czech" + note = "In Czech" } @article { jarnik:ojistem, @@ -130,7 +161,7 @@ volume = "VI", year = "1930", pages = "57--63", - note = "Czech" + note = "In Czech" } @book { tarjan:dsna, @@ -160,7 +191,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}", @@ -178,13 +219,33 @@ @article { karger:randomized, author = "D. R. Karger and P. N. Klein and R. E. Tarjan", - title = "{Linear expected-time algorithms for connectivity problems}", + title = "{A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees}", journal = jacm, volume = "42", + number = "2", pages = "321--328", year = "1995" } +@inproceedings { karger:sampling, + title={Random sampling in matroids, with applications to graph connectivity and minimum spanning trees}, + author={Karger, D.R.}, + booktitle={Proceedings of the 34th Annual Symposium on Foundations of Computer Science}, + year={1993}, + pages={84--93} +} + +@article{ chan:backward, + title={{Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees}}, + author={Chan, T.M.}, + journal={Information Processing Letters}, + volume={67}, + number={6}, + pages={303--304}, + year={1998}, + publisher={Elsevier} +} + @article { frederickson:online, author = "Greg N. Frederickson", title = "{Data structures for on-line updating of minimum spanning trees}", @@ -203,6 +264,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}, @@ -284,15 +357,6 @@ 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}, - pages={149--158}, - year={2003}, - publisher={ACM Press New York, NY, USA} -} - @article{ graham:msthistory, title={{On the history of the minimum spanning tree problem}}, author={Graham, R.L. and Hell, P.}, @@ -339,7 +403,7 @@ volume={206}, pages={310}, year={1938}, - note={French} + note={In French} } @incollection { sollin:mst, @@ -349,7 +413,7 @@ editor={Berge, C. and Ghouilla-Houri, A.}, publisher={Wiley, New York}, year={1965}, - note={French} + note={In French} } @article{ boyer:cutting, @@ -393,7 +457,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", @@ -413,7 +488,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}, @@ -448,7 +523,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", @@ -513,6 +588,15 @@ inproceedings{ pettie:minirand, 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}}, @@ -615,3 +699,898 @@ inproceedings{ pettie:minirand, 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={In 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} +} + +@article{ chazelle:mstapprox, + title={{Approximating the Minimum Spanning Tree Weight in Sublinear Time}}, + author={Chazelle, B. and Rubinfeld, R. and Trevisan, L.}, + journal={SIAM Journal on Computing}, + volume={34}, + pages={1370}, + year={2005}, + publisher={SIAM} +} + +@inproceedings{ czumaj:metric, + author = {Artur Czumaj and Christian Sohler}, + title = {Estimating the weight of metric minimum spanning trees in sublinear-time}, + booktitle = {STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing}, + year = {2004}, + isbn = {1-58113-852-0}, + pages = {175--183}, + location = {Chicago, IL, USA}, + doi = {http://doi.acm.org/10.1145/1007352.1007386}, + publisher = {ACM}, + address = {New York, NY, USA}, +} + +@inproceedings{ czumaj:euclidean, + author = {Artur Czumaj and Funda Erg\"{u}n and Lance Fortnow and Avner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler}, + title = {Sublinear-time approximation of Euclidean minimum spanning tree}, + booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms}, + year = {2003}, + isbn = {0-89871-538-5}, + pages = {813--822}, + location = {Baltimore, Maryland}, + publisher = {Society for Industrial and Applied Mathematics}, + address = {Philadelphia, PA, USA}, +} + +@book{ ieee:binfp, + author = {IEEE}, + title = {IEEE Standard 754-1985 for Binary Floating-point Arithmetic}, + year = {1985}, + publisher = {IEEE} +} + +@article{ dgoldberg:fp, + title={{What every computer scientist should know about floating-point arithmetic}}, + author={Goldberg, D.}, + journal={ACM Computing Surveys (CSUR)}, + volume={23}, + number={1}, + pages={5--48}, + year={1991}, + publisher={ACM Press New York, NY, USA} +} + +@article{ thorup:floatint, + title={{Floats, Integers, and Single Source Shortest Paths}}, + author={Thorup, M.}, + journal={Journal of Algorithms}, + volume={35}, + number={2}, + pages={189--201}, + year={2000}, + publisher={Academic Press} +} + +@article{ shamos:closest, + title={{Closest-point problems}}, + author={Shamos, M. I. and Hoey, D.}, + journal={Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science}, + pages={151--162}, + year={1975} +} + +@article{ fortune:voronoi, + title={{A sweepline algorithm for Voronoi diagrams}}, + author={Fortune, S.}, + journal={Algorithmica}, + volume={2}, + number={1}, + pages={153--174}, + year={1987}, + publisher={Springer} +} + +@article{ zhou:nodel, + title={{Efficient minimum spanning tree construction without Delaunay triangulation}}, + author={Zhou, H. and Shenoy, N. and Nicholls, W.}, + journal={Information Processing Letters}, + volume={81}, + number={5}, + pages={271--276}, + year={2002}, + publisher={Elsevier} +} + +@techreport{ eppstein:spanning, + title={{Spanning Trees and Spanners}}, + author={Eppstein, D.}, + year={1996}, + institution={Information and Computer Science, University of California, Irvine} +} + +@article{ garey:steiner, + title={{The Complexity of Computing Steiner Minimal Trees}}, + author={Garey, M.R. and Graham, R.L. and Johnson, D.S.}, + journal={SIAM Journal on Applied Mathematics}, + volume={32}, + number={4}, + pages={835--859}, + year={1977}, +} + +@article{ garey:rectisteiner, + title={{The Rectilinear Steiner Tree Problem is NP-Complete}}, + author={Garey, M.R. and Johnson, D.S.}, + journal={SIAM Journal on Applied Mathematics}, + volume={32}, + number={4}, + pages={826--834}, + year={1977}, +} + +@article{ proemel:steiner, + title={{A new approximation algorithm for the Steiner tree problem with performance ratio $5/3$}}, + author={Promel, H.J. and Steger, A.}, + journal={Journal of Algorithms}, + volume={36}, + pages={89--101}, + year={2000} +} + +@article{ arora:tspapx, + title={{Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems}}, + author={Arora, S.}, + journal={Journal of the ACM (JACM)}, + volume={45}, + number={5}, + pages={753--782}, + year={1998}, + publisher={ACM Press New York, NY, USA} +} + +@article{ harel:nca, + title={{Fast algorithms for finding nearest common ancestors}}, + author={Harel, D. and Tarjan, R.E.}, + journal={SIAM Journal on Computing}, + volume={13}, + number={2}, + pages={338--355}, + year={1984}, + publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA} +} + +@article{ gomoryhu, + author = "R. E. Gomory and T. C. Hu", + title = "Multi-Terminal Network Flows", + journal = "{Journal of SIAM}", + volume = {9}, + number = {4}, + year = {1961}, + pages = {551--570} +} + +@inproceedings{ bhalgat:ght, + author = {Ramesh Hariharan and Telikepalli Kavitha and Debmalya Panigrahi and Anand Bhalgat}, + title = {{An $\widehat\O(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs}}, + booktitle = {STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing}, + year = {2007}, + isbn = {978-1-59593-631-8}, + pages = {605--614}, + location = {San Diego, California, USA}, + doi = {http://doi.acm.org/10.1145/1250790.1250879}, + publisher = {ACM}, + address = {New York, NY, USA}, +} + +@article{ sleator:trees, + title={{A data structure for dynamic trees}}, + author={Sleator, D.D. and Tarjan, R.E.}, + journal={Journal of Computer and System Sciences}, + volume={26}, + number={3}, + pages={362--391}, + year={1983}, + publisher={Academic Press, Inc. Orlando, FL, USA} +} + +@article{ chernoff, + title={{A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations}}, + author={Chernoff, H.}, + journal={The Annals of Mathematical Statistics}, + volume={23}, + number={4}, + pages={493--507}, + 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}, +} + +@article{ tarjan:applpc, + author = {Robert Endre Tarjan}, + title = {Applications of Path Compression on Balanced Trees}, + journal = {Journal of the ACM}, + volume = {26}, + number = {4}, + year = {1979}, + issn = {0004-5411}, + pages = {690--715}, + doi = {http://doi.acm.org/10.1145/322154.322161}, + publisher = {ACM}, + address = {New York, NY, USA}, +}