+
+@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}
+}
+
+@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}
+}