X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=biblio.bib;h=765bf723ce34b59f47b7c7315ee55a814b743992;hb=ea5e11be97034d8e6b81c5eb28435cbbd5ee280e;hp=4fb17c083e3e9c4f55a23d43e781fb3805baab25;hpb=1bcd89eb4ae54a284a07aa6544f9a97fce85cb27;p=saga.git diff --git a/biblio.bib b/biblio.bib index 4fb17c0..765bf72 100644 --- a/biblio.bib +++ b/biblio.bib @@ -1,46 +1,65 @@ @inproceedings{ bender:lca, - author = "Michael A. Bender and Martin Farach-Colton", + 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" } + 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{ frederickson91ambivalent, +@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" } + 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}, + 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}, - publisher = {ACM Press}, - 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}, } @inproceedings { fw:transdich, author = "M. Fredman and D. E. Willard", title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}", - booktitle = "{Proceedings of FOCS'90}", + 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 = {Inf. Process. Lett.}, + title = {Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space}, + journal = {Information Processing Letters}, volume = {6}, number = {3}, year = {1977}, @@ -49,8 +68,8 @@ } @article{ benamram:pm, - author = "Ben-Amram, Amir M.", - title = "What is a ``Pointer Machine''?", + 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", @@ -69,16 +88,27 @@ @article{ chazelle:ackermann, author = "Bernard Chazelle", title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}", - journal = jacm, + 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" @@ -106,11 +136,11 @@ @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 mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}", + 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 = "Czech with German summary" + note = "In Czech with German summary" } @article { boruvka:networks, @@ -120,41 +150,32 @@ volume = "15", year = "1926", pages = "153--154", - note = "Czech" + 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 mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}", + 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 = "Czech" + note = "In Czech" } @book { tarjan:dsna, author = "Robert E. Tarjan", title = "{Data structures and network algorithms}", - series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}", + series = "{CMBS-NSF Regional Conference Series in Applied Mathematics}", volume = 44, year = "1983", - publisher = "SIAM" -} - -@article { gh:history, - author = "R. L. Graham and P. Hell", - title = "{On the history of the minimum spanning tree problem}", - journal = "{Annals of the History of Computing}", - volume = "7", - year = "1985", - pages = "43--57" + publisher = "Society for Industrial and Applied Mathematics" } @techreport { pettie:ackermann, author = "Seth Pettie", - title = "{Finding minimum spanning trees in $\O(m\alpha(m,n))$ time}", - institution = "Univ. of Texas at Austin", + title = "{Finding minimum spanning trees in $\O(m\timesalpha(m,n))$ time}", + institution = "University of Texas at Austin", year = "1999", number = "TR99-23", type = "Tech Report" @@ -163,7 +184,7 @@ @article{ pettie:optimal, author = {Seth Pettie and Vijaya Ramachandran}, title= {An optimal minimum spanning tree algorithm}, - journal = {Journal of the {ACM}}, + journal = {Journal of the ACM}, volume = {49}, number = {1}, year = {2002}, @@ -173,9 +194,8 @@ @inproceedings { pettie:optimal-conf, author = "Seth Pettie and Vijaya Ramachandran", title = "{An Optimal Minimum Spanning Tree Algorithm}", - booktitle = "{Proceedings of ICALP'2000}", + booktitle = "{Proceedings of ICALP 2000}", year = "2000", - publisher = "Springer Verlag", pages = "49--60" } @@ -189,7 +209,7 @@ @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 = jacm, + journal = "Journal of the ACM", volume = "42", number = "2", pages = "321--328", @@ -198,21 +218,20 @@ @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}, + 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.}, + author={Chan, T. M.}, journal={Information Processing Letters}, volume={67}, number={6}, pages={303--304}, year={1998}, - publisher={Elsevier} } @article { frederickson:online, @@ -228,6 +247,8 @@ 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" @@ -239,24 +260,22 @@ booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium", location = "Eilat, Israel, October 8--10, 2007", volume = "4698", - series = "Lecture Notes in Computer Science", + series = {{Lecture Notes in Computer Science}}, pages = "187--193", - publisher = "Springer", + 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 = {J. ACM}, + 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}, - publisher = {ACM Press}, - address = {New York, NY, USA}, } @article{ komlos:verify, @@ -273,10 +292,15 @@ @inproceedings{ king:verify, author = "Valerie King", title = "A Simpler Minimum Spanning Tree Verification Algorithm", - booktitle = "Workshop on Algorithms and Data Structures", + booktitle = "{Algorithms and Data Structures --- WADS '95: 4th International Workshop}", pages = "440--448", year = "1995", - url = "citeseer.ist.psu.edu/king95simpler.html" } + 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}}, @@ -299,36 +323,33 @@ @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}, + 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}, - publisher = {Society for Industrial and Applied Mathematics}, - address = {Philadelphia, PA, USA}, } @article{ kruskal:mst, title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}}, - author={Kruskal Jr, J.B.}, + 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 Berlin and Heidelberg GmbH \& Co.} + publisher={Springer Verlag} } @article{ graham:msthistory, title={{On the history of the minimum spanning tree problem}}, - author={Graham, R.L. and Hell, P.}, + author={Graham, R. L. and Hell, P.}, journal={Annals of the History of Computing}, volume={7}, number={1}, @@ -339,7 +360,7 @@ @article{ cayley:trees, title={{A theorem on trees}}, author={Cayley, Arthur}, - journal={Quart. J. Math}, + journal={Quarterly Journal of Mathematics}, volume={23}, year={1889}, pages={376--378} @@ -353,7 +374,7 @@ number={1}, pages={269--271}, year={1959}, - publisher={Springer} + publisher={Springer Verlag} } @article{ prim:mst, @@ -372,7 +393,7 @@ volume={206}, pages={310}, year={1938}, - note={French} + note={In French} } @incollection { sollin:mst, @@ -382,12 +403,12 @@ editor={Berge, C. and Ghouilla-Houri, A.}, publisher={Wiley, New York}, year={1965}, - note={French} + 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.}, + author={Boyer, J. M. and Myrvold, W. J.}, journal={Journal of Graph Algorithms and Applications}, volume={8}, number={3}, @@ -398,11 +419,11 @@ @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}, + booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON '99}, location={Tokyo, Japan}, year={1999}, pages={41--50}, - publisher={Springer}, + publisher={Springer Verlag}, series={{Lecture Notes in Computer Science}}, volume={1627} } @@ -414,14 +435,14 @@ location={Sydney, Australia}, year={2000}, pages={362--372}, - publisher={Springer}, + 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.}, + author={Leiserson, C. E. and Rivest, R. L. and Cormen, T. H. and Stein, C.}, year={2001}, publisher={McGraw-Hill} } @@ -441,7 +462,7 @@ author = "S. Pettie", title = "An inverse-{A}ckermann style lower bound for the online minimum spanning tree verification problem", - booktitle = "Proc. 43rd Annual Symp. on the Foundations of Computer Science, Vancouver, Canada", + 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" } @@ -449,7 +470,7 @@ @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 J. Comput.", + journal = "SIAM Journal of Computing", volume = "21", number = "6", pages = "1184-1192", @@ -457,25 +478,22 @@ 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 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}, - publisher = {Society for Industrial and Applied Mathematics}, - address = {Philadelphia, PA, USA} } -@article{ buchsbaum:verify, +@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.}, - journal={Proceedings of the thirtieth annual ACM Symposium on Theory of Computing}, + 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}, - publisher={ACM Press New York, NY, USA} } @article{ bacala:parametric, @@ -486,48 +504,45 @@ inproceedings{ pettie:minirand, 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 = "11th European Symposium on Algorithms (ESA)", - number = "2832", - series = "LNCS", + booktitle = "Algorithms --- ESA 2003: 11th European Symposium", + volume = "2832", + series = "Lecture Notes in Computer Science", pages = "679--690", - publisher = "Springer", + 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}}, + 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 fourteenth annual ACM symposium on Parallel algorithms and architectures}, + journal={Proceedings of the 14th annual ACM Symposium on Parallel algorithms and architectures}, pages={258--264}, year={2002}, - publisher={ACM Press New York, NY, USA} } @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.}, + 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} } -@Unpublished{ eisner:tutorial, +@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}, + 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/~jason/papers/#ms97}, + url = {http://cs.jhu.edu/{\char126}jason/papers/\#ms97}, } @article{ aho:lca, @@ -545,7 +560,6 @@ inproceedings{ pettie:minirand, year = {1997}, isbn = {0-201-89683-4}, publisher = {Addison Wesley Longman Publishing Co., Inc.}, - address = {Redwood City, CA, USA}, } @book{ knuth:seminalg, @@ -554,7 +568,6 @@ inproceedings{ pettie:minirand, year = {1997}, isbn = {978-0-201-89684-8}, publisher = {Addison Wesley Longman Publishing Co., Inc.}, - address = {Redwood City, CA, USA}, } @book{ knuth:sas, @@ -563,18 +576,15 @@ inproceedings{ pettie:minirand, 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}}, - booktitle = {STACS '98: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science}, + 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}, - publisher = {Springer-Verlag}, - address = {London, UK}, } @inproceedings{ cook:ram, @@ -585,8 +595,6 @@ inproceedings{ pettie:minirand, pages = {73--80}, location = {Denver, Colorado, United States}, doi = {http://doi.acm.org/10.1145/800152.804898}, - publisher = {ACM}, - address = {New York, NY, USA}, } @book{ okasaki:funcds, @@ -606,8 +614,8 @@ inproceedings{ pettie:minirand, @article{ hagerup:dd, title={{Deterministic Dictionaries}}, - author={Hagerup, T. and Miltersen, P.B. and Pagh, R.}, - journal={J. Algorithms}, + author={Hagerup, T. and Miltersen, P. B. and Pagh, R.}, + journal={Journal of Algorithms}, volume={41}, number={1}, pages={69--85}, @@ -616,13 +624,12 @@ inproceedings{ pettie:minirand, @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 (JACM)}, + 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}, - publisher={ACM Press New York, NY, USA} } @book{ motwani:randalg, @@ -634,45 +641,42 @@ inproceedings{ pettie:minirand, @article{ fw:fusion, title={{Surpassing the information theoretic bound with fusion trees}}, - author={Fredman, M.L. and Willard, D.E.}, + author={Fredman, M. L. and Willard, D. E.}, journal={Journal of Computer and System Sciences}, volume={47}, number={3}, pages={424--436}, year={1993}, - publisher={Academic Press, Inc. Orlando, FL, USA} } -@article{ han:detsort, +@inproceedings{ han:detsort, 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}, + booktitle={STOC 2002: Proceedings of the 34th annual ACM Symposium on Theory of Computing}, pages={602--608}, year={2002}, - publisher={ACM Press New York, NY, USA} } -@article{ hanthor:randsort, +@inproceedings{ hanthor:randsort, 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}, + booktitle={FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science}, pages={135--144}, year={2002}, - publisher={IEEE Computer Society Washington, DC, USA} } -@article{ ito:newrap, +@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.}, - journal={Proc. 12th IEEE Symp. Computer Arithmetic}, + booktitle={Proceedings of the 12th IEEE Symposium on Computer Arithmetic}, pages={2--9}, year={1995} } -@article{ brodnik:lsb, +@inproceedings{ 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}, + booktitle={Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia}, year={1993} } @@ -701,14 +705,14 @@ inproceedings{ pettie:minirand, number={4}, pages={265--268}, year={1967}, - publisher={Springer}, - note={German} + publisher={Springer Verlag}, + 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", + 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" @@ -716,7 +720,7 @@ inproceedings{ pettie:minirand, @article{ myrvold:rank, title={{Ranking and unranking permutations in linear time}}, - author={Myrvold, W.J. and Ruskey, F.}, + author={Myrvold, W. J. and Ruskey, F.}, journal={Information Processing Letters}, volume={79}, number={6}, @@ -735,15 +739,15 @@ inproceedings{ pettie:minirand, @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}, + 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 Sn}}, - author={Ruskey, F. and Savage, C.D.}, + 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}, @@ -763,9 +767,9 @@ inproceedings{ pettie:minirand, @book{ reingold:catp, title={{Combinatorial Algorithms: Theory and Practice}}, - author={Reingold, E.M.}, + author={Reingold, E. M.}, year={1977}, - publisher={Prentice Hall College Div} + publisher={Prentice Hall College Div.} } @inproceedings{ dietz:oal, @@ -775,8 +779,6 @@ inproceedings{ pettie:minirand, year = {1989}, isbn = {3-540-51542-9}, pages = {39--46}, - publisher = {Springer-Verlag}, - address = {London, UK}, } @book { ss:fifteen, @@ -794,7 +796,6 @@ inproceedings{ pettie:minirand, number={2}, pages={325--357}, year={2004}, - publisher={Academic Press, Inc. Orlando, FL, USA} } @book{ matnes:idm, @@ -804,22 +805,22 @@ inproceedings{ pettie:minirand, 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} +@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 Math. J}, + journal={Duke Mathematical Journal}, volume={13}, number={2}, pages={259--268}, - year={1946} + year={1946}, + publisher={Duke University Press} } @article{ dinic:flow, @@ -834,7 +835,6 @@ inproceedings{ pettie:minirand, @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}, @@ -864,22 +864,22 @@ inproceedings{ pettie:minirand, year={2004} } -@article{ kasteleyn:crystals, +/* 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.}, - journal={Graph Theory and Theoretical Physics}, + booktitle={Graph Theory and Theoretical Physics}, publisher={Academic Press, London}, pages={43--110}, year={1967} } -@article{ yuster:matching, +@inproceedings{ 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}, + booktitle={SODA 2007: Proceedings of the 18th 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, @@ -890,7 +890,6 @@ inproceedings{ pettie:minirand, number={1}, pages={3--20}, year={2006}, - publisher={Springer} } @article {lovasz:minors, @@ -904,34 +903,31 @@ inproceedings{ pettie:minirand, } @article{ andersson:fusion, - title={{Fusion trees can be implemented with AC0 instructions only}}, - author={Andersson, A. and Miltersen, P.B. and Thorup, M.}, + 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(Print)}, + journal={SIAM Journal on Computing}, 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}, + journal={STOC 2003: Proceedings of the 35th ACM Symposium on Theory of Computing}, pages={149--158}, year={2003}, - publisher={ACM Press New York, NY, USA} } @article{ chazelle:mstapprox, @@ -941,32 +937,25 @@ inproceedings{ pettie:minirand, 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}, + 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}, - 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}, + 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}, - location = {Baltimore, Maryland}, - publisher = {Society for Industrial and Applied Mathematics}, - address = {Philadelphia, PA, USA}, } @book{ ieee:binfp, @@ -979,12 +968,11 @@ inproceedings{ pettie:minirand, @article{ dgoldberg:fp, title={{What every computer scientist should know about floating-point arithmetic}}, author={Goldberg, D.}, - journal={ACM Computing Surveys (CSUR)}, + journal={ACM Computing Surveys}, volume={23}, number={1}, pages={5--48}, year={1991}, - publisher={ACM Press New York, NY, USA} } @article{ thorup:floatint, @@ -995,13 +983,12 @@ inproceedings{ pettie:minirand, 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}, + journal={FOCS '75: Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science}, pages={151--162}, year={1975} } @@ -1014,7 +1001,6 @@ inproceedings{ pettie:minirand, number={1}, pages={153--174}, year={1987}, - publisher={Springer} } @article{ zhou:nodel, @@ -1025,19 +1011,19 @@ inproceedings{ pettie:minirand, 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} + 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.}, + author={Garey, M. R. and Graham, R. L. and Johnson, D. S.}, journal={SIAM Journal on Applied Mathematics}, volume={32}, number={4}, @@ -1047,7 +1033,7 @@ inproceedings{ pettie:minirand, @article{ garey:rectisteiner, title={{The Rectilinear Steiner Tree Problem is NP-Complete}}, - author={Garey, M.R. and Johnson, D.S.}, + author={Garey, M. R. and Johnson, D. S.}, journal={SIAM Journal on Applied Mathematics}, volume={32}, number={4}, @@ -1057,7 +1043,7 @@ inproceedings{ pettie:minirand, @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.}, + author={Promel, H. J. and Steger, A.}, journal={Journal of Algorithms}, volume={36}, pages={89--101}, @@ -1067,23 +1053,21 @@ inproceedings{ pettie:minirand, @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)}, + journal={Journal of the ACM}, 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.}, + 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, @@ -1098,26 +1082,23 @@ inproceedings{ pettie:minirand, @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}, + 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}, - 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.}, + 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, @@ -1135,9 +1116,417 @@ inproceedings{ pettie:minirand, author = {Seth Pettie and Vijaya Ramachandran}, title = {A randomized time-work optimal parallel algorithm for finding a minimum spanning forest}, - journal = {SIAM J. Comput.}, + 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 Verlag}, + 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} +}