Yet more fixes to bibliography.

[saga.git] / biblio.bib

@inproceedings{ bender:lca,
    author = "Bender, M. A. and Farach-Colton, M.",
    title = "The {LCA} Problem Revisited",
    booktitle = "Latin American Theoretical {INformatics}",
    pages = "88--94",
    year = "2000",
    url = "citeseer.ist.psu.edu/bender00lca.html"
}

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

@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",
    year = "1991",
    url = "citeseer.ist.psu.edu/frederickson91ambivalent.html"
}

@article{ tarjan:wcsetunion,
 author = {Robert E. Tarjan and Jan van Leeuwen},
 title = {Worst-case Analysis of Set Union Algorithms},
 journal = {Journal of the ACM},
 volume = {31},
 number = {2},
 year = {1984},
 issn = {0004-5411},
 pages = {245--281},
 doi = {http://doi.acm.org/10.1145/62.2160},
}

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

@inproceedings { fw:transdich,
   author = "M. Fredman and D. E. Willard",
   title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}",
   booktitle={FOCS '90: Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science},
   pages = "719--725",
   year = "1990"
}

@article{ boas:vebt,
  author    = {Peter van Emde Boas},
  title     = {Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space},
  journal   = {Information Processing Letters},
  volume    = {6},
  number    = {3},
  year      = {1977},
  pages     = {80-82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@article{ benamram:pm,
    author = "Ben-Amram, A. M.",
    title = {{What is a ``Pointer Machine''?}},
    journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
    volume = "26",
    year = "1995",
    url = "citeseer.ist.psu.edu/ben-amram95what.html" }

@article{ matsui:planar,
    author = "Tomomi Matsui",
    title = "{The Minimum Spanning tree Problem on a Planar Graph}",
    journal = "Discrete Applied Mathematics",
    volume = "58",
    year = "1995",
    pages = "91--94",
    url = "citeseer.nj.nec.com/2319.html"
}

@article{ chazelle:ackermann,
    author = "Bernard Chazelle",
    title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
    journal = "Journal of the ACM",
    volume = "47",
    number = {6},
    pages = "1028--1047",
    year = "2000"
}

@inproceedings{ chazelle:almostacker,
  title={{A faster deterministic algorithm for minimum spanning trees}},
  author={Chazelle, Bernard},
  booktitle={FOCS '97: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science},
  pages={22},
  year={1997},
}

@article{ nesetril:history,
    author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
    title = "{Some remarks on the history of MST-problem}",
    journal = "Archivum Mathematicum",
    publisher = "Masaryk University",
    address = "Brno, Czech Republic",
    volume = "33",
    pages = "15--22",
    year = "1997"
}

@article{ nesetril:boruvka,
    author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
    title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
    journal = "Discrete Mathematics",
    volume = "233(1--3)",
    pages = "3--36",
    year = "2001"
}

@incollection { nesetril:minors,
    author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
    title = "{Colorings and Homomorphisms of Minor Closed Classes}",
    booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
    editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
    year = "2003",
    pages = "651--664",
    publisher = "Springer Verlag"
}

@article { boruvka:ojistem,
    author = "Otakar Bor{\accent23u}vka",
    title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
    journal = "Pr\'ace moravsk\'e p\v{r}\'\i{}rodov\v{e}deck\'e spole\v{c}nosti v~Brn\v{e}",
    volume = "III",
    year = "1926",
    pages = "37--58",
    note = "In Czech with German summary"
}

@article { boruvka:networks,
    author = "Otakar Bor{\accent23u}vka",
    title = "{P\v{r}\'\i{}sp\v{e}vek k~\v{r}e\v{s}en\'\i{} ot\'azky ekonomick\'e stavby elektrovodn\'y{}ch s\'\i{}t\'\i{} (Contribution to the solution of a problem of economical construction of electric networks)}",
    journal = "Elektronick\'y obzor",
    volume = "15",
    year = "1926",
    pages = "153--154",
    note = "In Czech"
}

@article { jarnik:ojistem,
    author = "Vojt\v{e}ch Jarn\'\i{}k",
    title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
    journal = "Pr\'ace moravsk\'e p\v{r}\'\i{}rodov\v{e}deck\'e spole\v{c}nosti v~Brn\v{e}",
    volume = "VI",
    year = "1930",
    pages = "57--63",
    note = "In Czech"
}

@book { tarjan:dsna,
    author = "Robert E. Tarjan",
    title = "{Data structures and network algorithms}",
    series = "{CMBS-NSF Regional Conference Series in Applied Mathematics}",
    volume = 44,
    year = "1983",
    publisher = "Society for Industrial and Applied Mathematics"
}

@techreport { pettie:ackermann,
    author = "Seth Pettie",
    title = "{Finding minimum spanning trees in $\O(m\timesalpha(m,n))$ time}",
    institution = "Univ. of Texas at Austin",
    year = "1999",
    number = "TR99-23",
    type = "Tech Report"
}

@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}",
   year = "2000",
   pages = "49--60"
}

@article { pettie:alpha,
  title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}},
  author={Pettie, S.},
  year={1999},
  publisher={University of Texas at Austin Austin, TX, USA}
}

@article { karger:randomized,
   author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
   title = "{A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees}",
   journal = "Journal of the ACM",
   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={FOCS '93: Proceedings of the 34th Annual IEEE 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},
}

@article { frederickson:online,
   author = "Greg N. Frederickson",
   title = "{Data structures for on-line updating of minimum spanning trees}",
   journal = "{SIAM Journal on Computing}",
   volume = "14",
   pages = "781--798",
   year = "1985"
}

@article { mm:mst,
   author = "Martin Mare\v{s}",
   title = "{Two linear time algorithms for MST on minor closed graph classes}",
   journal = "{Archivum Mathematicum}",
    publisher = "Masaryk University",
    address = "Brno, Czech Republic",
   volume = "40",
   pages = "315--320",
   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 Verlag",
  year = "2007",
}

@article{ ft:fibonacci,
 author = {Michael L. Fredman and Robert Endre Tarjan},
 title = {Fibonacci heaps and their uses in improved network optimization algorithms},
 journal = {Journal of the ACM},
 volume = {34},
 number = {3},
 year = {1987},
 issn = {0004-5411},
 pages = {596--615},
 doi = {http://doi.acm.org/10.1145/28869.28874},
 }

@article{ komlos:verify,
  author    = {J{\'a}nos Koml{\'o}s},
  title     = {Linear verification for spanning trees.},
  journal   = {Combinatorica},
  volume    = {5},
  number    = {1},
  year      = {1985},
  pages     = {57--65},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

@inproceedings{ king:verify,
    author = "Valerie King",
    title = "A Simpler Minimum Spanning Tree Verification Algorithm",
    booktitle = "{Algorithms and Data Structures --- WADS '95: 4th International Workshop}",
    pages = "440--448",
    year = "1995",
    location = "Kingston, Canada",
    volume = "955",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer Verlag",
    url = "citeseer.ist.psu.edu/king95simpler.html"
}

@article{ king:verifytwo,
  title={{A Simpler Minimum Spanning Tree Verification Algorithm}},
  author={King, Valerie},
  journal={Algorithmica},
  volume={18},
  pages={263--270},
  year={1997}
}

@book { schrijver,
    author = "Alexander Schrijver",
    title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
    series = "Algorithms and Combinatorics",
    volume = 24,
    year = 2003,
    publisher = "Springer Verlag"
}

@inproceedings{ thorup:aczero,
 author = {Mikkel Thorup},
 title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
 booktitle = {SODA 2003: Proceedings of the 14th annual ACM-SIAM Symposium on Discrete algorithms},
 year = {2003},
 isbn = {0-89871-538-5},
 pages = {699--707},
 location = {Baltimore, Maryland},
}

@article{ kruskal:mst,
  title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
  author={Kruskal, Jr, J. B.},
  journal={Proceedings of the American Mathematical Society},
  volume={7},
  number={1},
  pages={48--50},
  year={1956},
  publisher={JSTOR}
}

@book{ diestel:gt,
  title={{Graph Theory}},
  author={Diestel, R.},
  year={2005},
  publisher={Springer Verlag}
}

@article{ graham:msthistory,
  title={{On the history of the minimum spanning tree problem}},
  author={Graham, R. L. and Hell, P.},
  journal={Annals of the History of Computing},
  volume={7},
  number={1},
  pages={43--57},
  year={1985}
}

@article{ cayley:trees,
  title={{A theorem on trees}},
  author={Cayley, Arthur},
  journal={Quarterly Journal of Mathematics},
  volume={23},
  year={1889},
  pages={376--378}
}

@article{ dijkstra:mst,
  title={{A note on two problems in connexion with graphs}},
  author = "Dijkstra, E. W.",
  journal={Numerische Mathematik},
  volume={1},
  number={1},
  pages={269--271},
  year={1959},
  publisher={Springer Verlag}
}

@article{ prim:mst,
  author = "Prim, R. C.",
  title = "Shortest connection networks and some generalizations",
  journal = "Bell System Technical Journal",
  volume = "36",
  year = "1957",
  pages={567--574},
}

@article{ choquet:mst,
  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},
  note={In French}
}

@incollection { sollin:mst,
  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},
  note={In French}
}

@article{ boyer:cutting,
  title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
  author={Boyer, J. M. and Myrvold, W. J.},
  journal={Journal of Graph Algorithms and Applications},
  volume={8},
  number={3},
  pages={241--273},
  year={2004}
}

@inproceedings{ takaoka:twothree,
  title={{Theory of 2-3 Heaps}},
  author={Takaoka, T. and Christchurch, N. Z.},
  booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON '99},
  location={Tokyo, Japan},
  year={1999},
  pages={41--50},
  publisher={Springer Verlag},
  series={{Lecture Notes in Computer Science}},
  volume={1627}
}

@inproceedings{ takaoka:trinomial,
  title={{Theory of Trinomial Heaps}},
  author={Takaoka, Tadao},
  booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
  location={Sydney, Australia},
  year={2000},
  pages={362--372},
  publisher={Springer Verlag},
  series={{Lecture Notes in Computer Science}},
  volume={1858}
}

@book{ clrs,
  title={{Introduction to Algorithms}},
  author={Leiserson, C. E. and Rivest, R. L. and Cormen, T. H. and Stein, C.},
  year={2001},
  publisher={McGraw-Hill}
}

@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",
  booktitle = "FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science",
  year = "2002",
  url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
}

@article{ dixon:verify,
    author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
    title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
    journal = "SIAM Journal of Computing",
    volume = "21",
    number = "6",
    pages = "1184-1192",
    year = "1992",
    url = "citeseer.ist.psu.edu/dixon92verification.html"
}

@inproceedings{ pettie:minirand,
 author = {Seth Pettie and Vijaya Ramachandran},
 title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
 booktitle = {SODA 2002: Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms},
 year = {2002},
 isbn = {0-89871-513-X},
 pages = {713--722},
 location = {San Francisco, California},
}

@inproceedings{ 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.},
  booktitle={STOC 1998: Proceedings of the 30th annual ACM Symposium on Theory of Computing},
  pages={279--288},
  year={1998},
}

@article{ bacala:parametric,
  title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
  author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
  journal={Theoretical Computer Science},
  volume={181},
  number={1},
  pages={57--74},
  year={1997},
  publisher={Elsevier}
}

@inproceedings{ katriel:cycle,
  author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
  title = "A practical minimum spanning tree algorithm using the cycle property",
  booktitle = "Algorithms --- ESA 2003: 11th European Symposium",
  volume = "2832",
  series = "Lecture Notes in Computer Science",
  pages = "679--690",
  publisher = "Springer Verlag",
  year = "2003",
  url = "citeseer.ist.psu.edu/katriel03practical.html"
}

@article{ alstrup:nca,
  title={{Nearest Common Ancestors: A Survey and a new Distributed Algorithm}},
  author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
  journal={Proceedings of the 14th annual ACM Symposium on Parallel algorithms and architectures},
  pages={258--264},
  year={2002},
}

@article{ gabow:mst,
  title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
  author={Gabow, H. N. and Galil, Z. and Spencer, T. and Tarjan, R. E.},
  journal={Combinatorica},
  volume={6},
  number={2},
  pages={109--122},
  year={1986},
  publisher={Springer Verlag}
}

@online{ eisner:tutorial,
  author =       {Jason Eisner},
  title =        {{State-of-the-Art Algorithms for Minimum Spanning
                  Trees: A~Tutorial Discussion}},
  note =         {Manuscript available online (78 pages), University of Pennsylvania},
  year =         1997,
  url =          {http://cs.jhu.edu/{\char126}jason/papers/\#ms97},
}

@article{ aho:lca,
  title={{On finding lowest common ancestors in trees.}},
  author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
  journal={SIAM Journal on Computing},
  volume={5},
  pages={115--132},
  year={1976}
}

@book{ knuth:fundalg,
 author = {Donald E. Knuth},
 title = {The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms},
 year = {1997},
 isbn = {0-201-89683-4},
 publisher = {Addison Wesley Longman Publishing Co., Inc.},
}

@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.},
}

@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.},
}

@inproceedings{ hagerup:wordram,
 author = {Torben Hagerup},
 title = {{Sorting and Searching on the Word RAM}},
 booktitle = {STACS '98: Proceedings of the 15th annual Symposium on Theoretical Aspects of Computer Science},
 year = {1998},
 isbn = {3-540-64230-7},
 pages = {366--398},
}

@inproceedings{ cook:ram,
 author = {Stephen A. Cook and Robert A. Reckhow},
 title = {Time-bounded random access machines},
 booktitle = {STOC '72: Proceedings of the fourth annual ACM Symposium on Theory of Computing},
 year = {1972},
 pages = {73--80},
 location = {Denver, Colorado, United States},
 doi = {http://doi.acm.org/10.1145/800152.804898},
}

@book{ okasaki:funcds,
  author = {Chris Okasaki},
  title = {Purely Functional Data Structures},
  year = {1999},
  publisher = {Cambridge University Press}
}

@book { intel:pentium,
  author = {{Intel Corp.}},
  title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference},
  year = {2007},
  publisher = {Intel Corp.},
  xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
}

@article{ hagerup:dd,
  title={{Deterministic Dictionaries}},
  author={Hagerup, T. and Miltersen, P. B. and Pagh, R.},
  journal={Journal of Algorithms},
  volume={41},
  number={1},
  pages={69--85},
  year={2001}
}

@article{ fredman:sst,
  title={{Storing a Sparse Table with $\O(1)$ Worst Case Access Time}},
  author={Fredman, M. L. and Koml{\'o}s, J. and Szemer{\'e}di, E.},
  journal={Journal of the ACM},
  volume={31},
  number={3},
  pages={538--544},
  year={1984},
}

@book{ motwani:randalg,
  title={{Randomized Algorithms}},
  author={Motwani, R. and Raghavan, P.},
  year={1995},
  publisher={Cambridge University Press}
}

@article{ fw:fusion,
  title={{Surpassing the information theoretic bound with fusion trees}},
  author={Fredman, M. L. and Willard, D. E.},
  journal={Journal of Computer and System Sciences},
  volume={47},
  number={3},
  pages={424--436},
  year={1993},
}

@inproceedings{ han:detsort,
  title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}},
  author={Han, Y.},
  booktitle={STOC 2002: Proceedings of the 34th annual ACM Symposium on Theory of Computing},
  pages={602--608},
  year={2002},
}

@inproceedings{ hanthor:randsort,
  title={{Integer Sorting in $\O(n\sqrt{\log\log n})$ Expected Time and Linear Space}},
  author={Han, Y. and Thorup, M.},
  booktitle={FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science},
  pages={135--144},
  year={2002},
}

@inproceedings{ ito:newrap,
  title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}},
  author={Ito, M. and Takagi, N. and Yajima, S.},
  booktitle={Proceedings of the 12th IEEE Symposium on Computer Arithmetic},
  pages={2--9},
  year={1995}
}

@inproceedings{ brodnik:lsb,
  title={{Computation of the least significant set bit}},
  author={Brodnik, A.},
  booktitle={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 Verlag},
  note={In German}
}

@inproceedings{ gustedt:parallel,
    author = "Jens Gustedt",
    title = "Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel",
    booktitle = "STACS '98: Proceedings of the 15th annual 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 Applied Mathematics},
  volume={57},
  pages={75--83},
  year={1995}
}

@article{ ruskey:hce,
  title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n$}},
  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},
}

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

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

@book{ stanley:econe,
  title={{Enumerative Combinatorics. Vol. 1 (2nd ed.)}},
  author={Stanley, R. P.},
  publisher={Cambridge University Press},
  year={2000}
}

@article{ kaplansky:rooks,
  title={{The problem of the rooks and its applications}},
  author={Kaplansky, I. and Riordan, J.},
  journal={Duke Mathematical Journal},
  volume={13},
  number={2},
  pages={259--268},
  year={1946},
  publisher={Duke University Press}
}

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

/* HACK: bibtex cannot handle a part of a book with its own name */
@inproceedings{ kasteleyn:crystals,
  title={{Graph theory and crystal physics}},
  author={Kasteleyn, P. W.},
  booktitle={Graph Theory and Theoretical Physics},
  publisher={Academic Press, London},
  pages={43--110},
  year={1967}
}

@inproceedings{ yuster:matching,
  title={{Maximum matching in graphs with an excluded minor}},
  author={Yuster, R. and Zwick, U.},
  booktitle={SODA 2007: Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms},
  pages={108--117},
  year={2007},
}

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

@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 AC$^0$ 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},
  volume={30},
  number={1},
  pages={86--109},
  year={2001},
}

@article{ thorup:pqsssp,
  title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
  author={Thorup, M.},
  journal={STOC 2003: Proceedings of the 35th ACM Symposium on Theory of Computing},
  pages={149--158},
  year={2003},
}

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

@inproceedings{ czumaj:metric,
 author = {Artur Czumaj and Christian Sohler},
 title = {Estimating the weight of metric minimum spanning trees in sublinear-time},
 booktitle = {STOC 2004: Proceedings of the 36th annual ACM Symposium on Theory of Computing},
 year = {2004},
 isbn = {1-58113-852-0},
 pages = {175--183},
 location = {Chicago, IL, 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 2003: Proceedings of the 14th annual ACM-SIAM Symposium on Discrete Algorithms},
 year = {2003},
 isbn = {0-89871-538-5},
 pages = {813--822},
 publisher = {Society for Industrial and Applied Mathematics},
}

@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},
  volume={23},
  number={1},
  pages={5--48},
  year={1991},
}

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

@article{ shamos:closest,
  title={{Closest-point problems}},
  author={Shamos, M. I. and Hoey, D.},
  journal={FOCS '75: 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},
}

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

@techreport{ eppstein:spanning,
  title={{Spanning Trees and Spanners}},
  author={Eppstein, D.},
  year={1996},
  institution={Information and Computer Science, University of California, Irvine},
  number = {96-16},
}

@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},
  volume={45},
  number={5},
  pages={753--782},
  year={1998},
}

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

@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 $\widetilde\O(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs}},
 booktitle = {STOC 2007: Proceedings of the 39th 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},
}

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

@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 Journal of Computing},
 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 = {Journal of the ACM},
 volume = {47},
 number = {6},
 year = {2000},
 issn = {0004-5411},
 pages = {1012--1027},
 doi = {http://doi.acm.org/10.1145/355541.355554},
}

@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 = {Journal of Algorithms},
 volume = {27},
 number = {2},
 year = {1998},
 issn = {0196-6774},
 pages = {170--217},
 doi = {http://dx.doi.org/10.1006/jagm.1997.0917},
}

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

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

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

@inproceedings{ alstrup:marked,
  title={{Marked ancestor problems}},
  author={Alstrup, S. and Husfeldt, T. and Rauhe, T.},
  booktitle={FOCS '98: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science},
  pages={534--543},
  year={1998}
}

@inproceedings{ arvind:isomorph,
  title={{Graph isomorphism is in SPP}},
  author={Arvind, V. and Kurur, P. P.},
  booktitle={FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science},
  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},
  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 21st 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},
}

@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},
  volume={48},
  number={4},
  pages={723--760},
  year={2001},
}

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

@inproceedings{ henzinger:mst,
  title={{Maintaining minimum spanning trees in dynamic graphs}},
  author={Henzinger, M. R. and King, V.},
  booktitle={ICALP '97: Proceedings of the 24th International Colloquium on Automata, Languages and Programming},
  pages={594--604},
  year={1997},
}

@mastersthesis { mares:dga,
  title={{Dynamick\'e grafov\'e algoritmy (Dynamic Graph Algorithms)}},
  author={Martin Mare\v{s}},
  school={Charles University in Prague, Faculty of Math and Physics},
  year={2000},
  note={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 Center},
  number = {1997-004},
  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},
  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 Verlag}
}

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

@inproceedings{ thorup:nearopt,
 author = {Mikkel Thorup},
 title = {Near-optimal fully-dynamic graph connectivity},
 booktitle = {STOC 2000: Proceedings of the 32nd 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},
}

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

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

@inproceedings{ hagerup:sssp,
  author = {Torben Hagerup},
  title = {{Improved Shortest Paths on the Word RAM}},
  booktitle = {ICALP 2000: Proceedings of the 27th International Colloquium on Automata, Languages and Programming},
  year = {2000},
  isbn = {3-540-67715-1},
  pages = {61--72},
}

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

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

@inproceedings{ pettie:pairing,
  author = {Seth Pettie},
  title = {Towards a Final Analysis of Pairing Heaps},
  booktitle = {FOCS 2005: Proceedings of the 46rd Annual IEEE Symposium on Foundations of Computer Science},
  year = {2005},
  pages = {174-183},
}

@book{ jaja:parallel,
  title={{An introduction to parallel algorithms}},
  author={J{\'a}J{\'a}, J.},
  year={1992},
  publisher={Addison Wesley Longman Publishing Co., Inc.}
}

@techreport { mm:ga,
  author = "Martin Mare\v{s}",
  title = "{Krajinou grafov\'ych algoritm\accent23u (Through the Landscape of Graph Algorithms)}",
  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 (The 54th Year of the Math Olympiad at High Schools)},
  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},
}

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

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