-@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},
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}",
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''?",
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}",
volume = "III",
year = "1926",
pages = "37--58",
- note = "Czech with German summary"
+ note = "In Czech with German summary"
}
@article { boruvka:networks,
volume = "15",
year = "1926",
pages = "153--154",
- note = "Czech"
+ note = "In Czech"
}
@article { jarnik:ojistem,
volume = "VI",
year = "1930",
pages = "57--63",
- note = "Czech"
+ note = "In Czech"
}
@book { tarjan:dsna,
@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",
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}",
@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}",
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},
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},
title={{Graph Theory}},
author={Diestel, R.},
year={2005},
- publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K}
-}
-
-@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}
+ publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.}
}
@article{ graham:msthistory,
}
@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={In 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={In French}
}
@article{ boyer:cutting,
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",
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},
+ booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2002},
isbn = {0-89871-513-X},
pages = {713--722},
@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}
@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",
@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},
+}
+
+@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}},
@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},
}
@article{ fredman:sst,
- title={{Storing a Sparse Table with 0 (1) Worst Case Access Time}},
+ 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},
}
@article{ han:detsort,
- title={{Deterministic sorting in O (nlog log n) time and linear space}},
+ 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},
+ 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 0 (n sqrt (log log n)) Expected Time and Linear Space}},
+ 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}
+}
+
+@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},
+}
+
+@article{ kostochka:lbh,
+ title={{Lower bound of the hadwiger number of graphs by their average degree}},
+ author={Kostochka, A.V.},
+ journal={Combinatorica},
+ volume={4},
+ number={4},
+ pages={307--316},
+ year={1984},
+ publisher={Springer}
+}
+
+@article{ thomason:efc,
+ title={{An extremal function for contractions of graphs}},
+ author={Thomason, A.},
+ journal={Mathematical proceedings of the Cambridge Philosophical Society},
+ volume={95},
+ number={2},
+ pages={261--265},
+ year={1984},
+ publisher={Cambridge University Press}
+}