From 4b61d025c4af1423b8b1c6603953a651607db816 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 3 May 2008 22:14:14 +0200 Subject: [PATCH] First part of corrections of bibliography. --- biblio.bib | 204 ++++++++++++++++++++++------------------------------- macros.tex | 2 +- pref.tex | 2 +- 3 files changed, 85 insertions(+), 123 deletions(-) diff --git a/biblio.bib b/biblio.bib index 9a40c05..37f4677 100644 --- a/biblio.bib +++ b/biblio.bib @@ -1,5 +1,5 @@ @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", @@ -9,7 +9,7 @@ @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}, + journal={SIAM Journal on Computing}, volume={26}, number={2}, pages={484--538}, @@ -28,7 +28,7 @@ @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}, @@ -41,7 +41,7 @@ @article{ tarjan:setunion, title={{Efficiency of a Good But Not Linear Set Union Algorithm}}, - author={Tarjan, R.E.}, + author={Tarjan, R. E.}, journal={Journal of the ACM}, volume={22}, number={2}, @@ -53,7 +53,7 @@ @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 Symposium on Foundations of Computer Science}, pages = "719--725", year = "1990" } @@ -71,8 +71,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", @@ -93,17 +93,17 @@ title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}", journal = jacm, volume = "47", + number = {6}, pages = "1028--1047", year = "2000" } -@article{ chazelle:almostacker, +@inproceedings{ chazelle:almostacker, title={{A faster deterministic algorithm for minimum spanning trees}}, author={Chazelle, B.}, - journal={Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS'97)}, + booktitle={FOCS '97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science}, pages={22}, year={1997}, - publisher={IEEE Computer Society Washington, DC, USA} } @article{ nesetril:history, @@ -137,7 +137,7 @@ @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", @@ -173,15 +173,6 @@ 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" -} - @techreport { pettie:ackermann, author = "Seth Pettie", title = "{Finding minimum spanning trees in $\O(m\alpha(m,n))$ time}", @@ -194,7 +185,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}, @@ -204,7 +195,7 @@ @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" @@ -229,7 +220,7 @@ @inproceedings { karger:sampling, title={Random sampling in matroids, with applications to graph connectivity and minimum spanning trees}, - author={Karger, D.R.}, + author={Karger, D. R.}, booktitle={Proceedings of the 34th Annual Symposium on Foundations of Computer Science}, year={1993}, pages={84--93} @@ -237,7 +228,7 @@ @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}, @@ -279,15 +270,13 @@ @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, @@ -330,7 +319,7 @@ @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 '03: Proceedings of the 14th annual ACM-SIAM symposium on Discrete algorithms}, year = {2003}, isbn = {0-89871-538-5}, pages = {699--707}, @@ -341,7 +330,7 @@ @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}, @@ -354,12 +343,12 @@ 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}, @@ -370,7 +359,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} @@ -418,7 +407,7 @@ @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}, @@ -429,7 +418,7 @@ @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}, @@ -452,7 +441,7 @@ @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} } @@ -480,7 +469,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", @@ -491,7 +480,7 @@ @inproceedings{ pettie:minirand, author = {Seth Pettie and Vijaya Ramachandran}, title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms}, - booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms}, + booktitle = {SODA '02: Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms}, year = {2002}, isbn = {0-89871-513-X}, pages = {713--722}, @@ -500,13 +489,12 @@ 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, @@ -533,17 +521,16 @@ } @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}, @@ -554,8 +541,8 @@ @Unpublished{ eisner:tutorial, author = {Jason Eisner}, - title = {State-of-the-Art Algorithms for Minimum Spanning - Trees: A Tutorial Discussion}, + 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}, @@ -604,8 +591,6 @@ year = {1998}, isbn = {3-540-64230-7}, pages = {366--398}, - publisher = {Springer-Verlag}, - address = {London, UK}, } @inproceedings{ cook:ram, @@ -616,8 +601,6 @@ 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, @@ -637,8 +620,8 @@ @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}, @@ -647,8 +630,8 @@ @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}, @@ -665,7 +648,7 @@ @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}, @@ -677,19 +660,17 @@ @article{ 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}, + journal={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={Proceedings of the 43rd Symposium on Foundations of Computer Science}, pages={135--144}, year={2002}, - publisher={IEEE Computer Society Washington, DC, USA} } @article{ ito:newrap, @@ -700,10 +681,10 @@ 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} } @@ -747,7 +728,7 @@ @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}, @@ -774,7 +755,7 @@ @article{ ruskey:hce, title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn}}, - author={Ruskey, F. and Savage, C.D.}, + author={Ruskey, F. and Savage, C. D.}, journal={SIAM Journal on Discrete Mathematics}, volume={6}, number={1}, @@ -794,7 +775,7 @@ @book{ reingold:catp, title={{Combinatorial Algorithms: Theory and Practice}}, - author={Reingold, E.M.}, + author={Reingold, E. M.}, year={1977}, publisher={Prentice Hall College Div} } @@ -806,8 +787,6 @@ year = {1989}, isbn = {3-540-51542-9}, pages = {39--46}, - publisher = {Springer-Verlag}, - address = {London, UK}, } @book { ss:fifteen, @@ -837,7 +816,7 @@ @article{ stanley:econe, title={{Enumerative combinatorics. Vol. 1}}, - author={Stanley, R.P.}, + author={Stanley, R. P.}, journal={Cambridge Studies in Advanced Mathematics}, volume={49}, year={1997} @@ -907,7 +886,7 @@ @article{ yuster:matching, title={{Maximum matching in graphs with an excluded minor}}, author={Yuster, R. and Zwick, U.}, - journal={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms}, + journal={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} @@ -935,8 +914,8 @@ } @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}, @@ -948,7 +927,7 @@ @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}, @@ -959,10 +938,9 @@ @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={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, @@ -978,26 +956,21 @@ @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 '04: 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}, + booktitle = {SODA '03: 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, @@ -1010,12 +983,11 @@ @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, @@ -1063,12 +1035,13 @@ 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}, @@ -1078,7 +1051,7 @@ @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}, @@ -1088,7 +1061,7 @@ @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}, @@ -1098,17 +1071,16 @@ @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}, @@ -1130,19 +1102,17 @@ @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}, + booktitle = {STOC '07: 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}, @@ -1166,7 +1136,7 @@ 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}, @@ -1176,21 +1146,19 @@ @article{ chazelle:softheap, author = {Bernard Chazelle}, title = {The soft heap: an approximate priority queue with optimal error rate}, - journal = {J. ACM}, + 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}, - 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}, + journal = {Journal of Algorithms}, volume = {27}, number = {2}, year = {1998}, @@ -1224,7 +1192,7 @@ @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.}, + 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}, @@ -1242,8 +1210,6 @@ 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, @@ -1271,15 +1237,15 @@ @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}, + journal={FOCS '98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science}, pages={534--543}, year={1998} } -@article{ arvind:isomorph, +@inproceedings{ 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}, + booktitle={FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science}, pages={743--750}, year={2002} } @@ -1309,7 +1275,7 @@ @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}, + booktitle = {STOC '89: Proceedings of the 21st annual ACM Symposium on Theory of Computing}, year = {1989}, isbn = {0-89791-307-8}, pages = {345--354}, @@ -1321,7 +1287,7 @@ @article{ henzinger:randdyn, title={{Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation}}, - author={Henzinger, M.R. and King, V.}, + author={Henzinger, M. R. and King, V.}, journal={Journal of the ACM}, volume={46}, number={4}, @@ -1332,7 +1298,7 @@ @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)}, + journal={Journal of the ACM}, volume={48}, number={4}, pages={723--760}, @@ -1351,7 +1317,7 @@ @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.}, + author={Eppstein, D. and Galil, Z. and Italiano, G. F. and Nissenzweig, A.}, journal={Journal of the ACM}, volume={44}, number={5}, @@ -1362,7 +1328,7 @@ @article{ henzinger:mst, title={{Maintaining minimum spanning trees in dynamic graphs}}, - author={Henzinger, M.R. and King, V.}, + author={Henzinger, M. R. and King, V.}, journal={Proceedings of the 24th International Colloquium on Automata, Languages and Programming}, pages={594--604}, year={1997}, @@ -1381,10 +1347,8 @@ 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}, + institution = {Digital Equipment Corp., Systems Research Center}, number = {1997-004}, - month = {12 Jun}, year = {1997}, url = {http://gatekeeper.dec.com/pub/DEC/SRC/technical-notes/abstracts/src-tn-1997-004.html} } @@ -1424,7 +1388,7 @@ @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}, + booktitle = {STOC '00: Proceedings of the 32nd annual ACM Symposium on Theory of Computing}, year = {2000}, isbn = {1-58113-184-4}, pages = {343--350}, @@ -1471,13 +1435,11 @@ @inproceedings{ hagerup:sssp, author = {Torben Hagerup}, - title = {Improved Shortest Paths on the Word RAM}, + 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, @@ -1491,7 +1453,7 @@ @book{ oxley:matroids, title={{Matroid Theory}}, - author={Oxley, J.G.}, + author={Oxley, J. G.}, year={1992}, publisher={Oxford University Press} } @@ -1531,7 +1493,7 @@ @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.}, + author={Fredman, M. L. and Sedgewick, R. and Sleator, D. D. and Tarjan, R. E.}, journal={Algorithmica}, volume={1}, number={1}, @@ -1597,7 +1559,7 @@ @article{ kostochka:lbh, title={{Lower bound of the hadwiger number of graphs by their average degree}}, - author={Kostochka, A.V.}, + author={Kostochka, A. V.}, journal={Combinatorica}, volume={4}, number={4}, diff --git a/macros.tex b/macros.tex index e4011ae..b4c1a2d 100644 --- a/macros.tex +++ b/macros.tex @@ -493,7 +493,7 @@ %%% Bibliography %%% %\bibliographystyle{abbrv} -\bibliographystyle{alpha} +\bibliographystyle{mjalpha} \def\dumpbib{ \def\bblhook{\parskip=2pt plus 1pt minus 0.5pt} \bibliography{biblio} diff --git a/pref.tex b/pref.tex index dfb726e..4cbc01a 100644 --- a/pref.tex +++ b/pref.tex @@ -21,7 +21,7 @@ ones, and last, but not least filling in important details where the original authors have missed some. When compared with the earlier surveys on the minimum spanning trees, most -notably Graham and Hell \cite{gh:history} and Eisner \cite{eisner:tutorial}, +notably Graham and Hell \cite{graham:msthistory} and Eisner \cite{eisner:tutorial}, this work adds many of the recent advances, the dynamic algorithms and also the relationship with computational models. No previous work covering the ranking problems in their entirety is known. -- 2.39.2