-@inproceedings{ bender00lca,
+@inproceedings{ bender:lca,
author = "Michael A. Bender and Martin Farach-Colton",
title = "The {LCA} Problem Revisited",
booktitle = "Latin American Theoretical {INformatics}",
- pages = "88-94",
+ pages = "88--94",
year = "2000",
url = "citeseer.ist.psu.edu/bender00lca.html" }
author = "Greg N. Frederickson",
title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
booktitle = "{IEEE} Symposium on Foundations of Computer Science",
- pages = "632-641",
+ pages = "632--641",
year = "1991",
url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" }
year = "1990"
}
-@article{boas77,
+@article{ boas:vebt,
author = {Peter van Emde Boas},
title = {Preserving Order in a Forest in Less Than Logarithmic Time
and Linear Space.},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
-@inproceedings{thorup03ac0,
- author = {Mikkel Thorup},
- title = {On AC0 implementations of fusion trees and atomic heaps},
- booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
- year = {2003},
- isbn = {0-89871-538-5},
- pages = {699--707},
- location = {Baltimore, Maryland},
- publisher = {Society for Industrial and Applied Mathematics},
- address = {Philadelphia, PA, USA},
- }
-
-@article{ benamram95what,
- author = "Ben-Amram",
+@article{ benamram:pm,
+ author = "Ben-Amram, Amir M.",
title = "What is a ``Pointer Machine''?",
journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
volume = "26",
@techreport { pettie:ackermann,
author = "Seth Pettie",
- title = "{Finding minimum spanning trees in $O(m\alpha(m,n))$ time}",
+ title = "{Finding minimum spanning trees in $\O(m\alpha(m,n))$ time}",
institution = "Univ. of Texas at Austin",
year = "1999",
number = "TR99-23",
year = "2004"
}
+@inproceedings{ mm:rank,
+ author = "Martin Mare\v{s} and Milan Straka",
+ title = "Linear-Time Ranking of Permutations",
+ booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium",
+ location = "Eilat, Israel, October 8--10, 2007",
+ volume = "4698",
+ series = "Lecture Notes in Computer Science",
+ pages = "187--193",
+ publisher = "Springer",
+ year = "2007",
+}
+
@article{ ft:fibonacci,
author = {Michael L. Fredman and Robert Endre Tarjan},
title = {Fibonacci heaps and their uses in improved network optimization algorithms},
publisher = "Springer Verlag"
}
-@inproceedings{ thorup:ac0,
+@inproceedings{ thorup:aczero,
author = {Mikkel Thorup},
title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
title={{Graph Theory}},
author={Diestel, R.},
year={2005},
- publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K}
-}
-
-@article{ thorup:pq,
- title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
- author={Thorup, M.},
- journal={Proceedings of the thirty-fifth ACM symposium on Theory of computing},
- pages={149--158},
- year={2003},
- publisher={ACM Press New York, NY, USA}
+ publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.}
}
@article{ graham:msthistory,
}
@article{ choquet:mst,
- title={{Etude de certains r{\'e}seaux de routes (in French)}},
+ title={{Etude de certains r{\'e}seaux de routes}},
author={Choquet, Gustave},
journal={Comptes-rendus de l'Académie des Sciences},
volume={206},
pages={310},
- year={1938}
+ year={1938},
+ note={French}
}
@incollection { sollin:mst,
- title={{Le trace de canalisation (in French)}},
+ title={{Le trace de canalisation}},
author={Sollin, M.},
booktitle={Programming, Games, and Transportation Networks},
editor={Berge, C. and Ghouilla-Houri, A.},
publisher={Wiley, New York},
- year={1965}
+ year={1965},
+ note={French}
}
@article{ boyer:cutting,
inproceedings{ pettie:minirand,
author = {Seth Pettie and Vijaya Ramachandran},
title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
- booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms},
+ booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms},
year = {2002},
isbn = {0-89871-513-X},
pages = {713--722},
@article{ buchsbaum:verify,
title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
author={Buchsbaum, A.L. and Kaplan, H. and Rogers, A. and Westbrook, J.R.},
- journal={Proceedings of the thirtieth annual ACM symposium on Theory of computing},
+ journal={Proceedings of the thirtieth annual ACM Symposium on Theory of Computing},
pages={279--288},
year={1998},
publisher={ACM Press New York, NY, USA}
@inproceedings{ katriel:cycle,
author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
title = "A practical minimum spanning tree algorithm using the cycle property",
- booktitle = "11th European Symposium on Algorithms(ESA)",
+ booktitle = "11th European Symposium on Algorithms (ESA)",
number = "2832",
series = "LNCS",
pages = "679--690",
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 fourteenth 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.},
+ journal={Combinatorica},
+ volume={6},
+ number={2},
+ pages={109--122},
+ year={1986},
+ publisher={Springer}
+}
+
+@Unpublished{ 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/~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.},
+ address = {Redwood City, CA, USA},
+}
+
+@book{ knuth:seminalg,
+ author = {Donald E. Knuth},
+ title = {The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical algorithms},
+ year = {1997},
+ isbn = {978-0-201-89684-8},
+ publisher = {Addison Wesley Longman Publishing Co., Inc.},
+ address = {Redwood City, CA, USA},
+}
+
+@book{ knuth:sas,
+ author = {Donald E. Knuth},
+ title = {{The Art of Computer Programming, Volume 3 (2nd ed.): Sorting and Searching}},
+ year = {1998},
+ isbn = {978-0-201-89685-5},
+ publisher = {Addison Wesley Longman Publishing Co., Inc.},
+ address = {Redwood City, CA, USA},
+}
+
+@inproceedings{ hagerup:wordram,
+ author = {Torben Hagerup},
+ title = {{Sorting and Searching on the Word RAM}},
+ 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,
+ 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},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
+
+@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={J. 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 (JACM)},
+ volume={31},
+ number={3},
+ pages={538--544},
+ year={1984},
+ publisher={ACM Press New York, NY, USA}
+}
+
+@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},
+ publisher={Academic Press, Inc. Orlando, FL, USA}
+}
+
+@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},
+ pages={602--608},
+ year={2002},
+ publisher={ACM Press New York, NY, USA}
+}
+
+@article{ 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},
+ pages={135--144},
+ year={2002},
+ publisher={IEEE Computer Society Washington, DC, USA}
+}
+
+@article{ ito:newrap,
+ title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}},
+ author={Ito, M. and Takagi, N. and Yajima, S.},
+ journal={Proc. 12th IEEE Symp. Computer Arithmetic},
+ pages={2--9},
+ year={1995}
+}
+
+@article{ brodnik:lsb,
+ title={{Computation of the least significant set bit}},
+ author={Brodnik, A.},
+ journal={Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia},
+ year={1993}
+}
+
+@article{ turan:succinct,
+ title={{Succinct representation of graphs.}},
+ author={Tur\'an, G.},
+ journal={Discrete Applied Mathematics},
+ volume={8},
+ number={3},
+ pages={289--294},
+ year={1984}
+}
+
+@book{ jones:haskell,
+ title={{Haskell 98 Language and Libraries: The Revised Report}},
+ author={Jones, P. and Simon, L.},
+ year={2003},
+ publisher={Cambridge University Press}
+}
+
+@article{ mader:dens,
+ title={{Homomorphieeigenschaften und mittlere Kantendichte von Graphen}},
+ author={Mader, W.},
+ journal={Mathematische Annalen},
+ volume={174},
+ number={4},
+ pages={265--268},
+ year={1967},
+ publisher={Springer},
+ note={German}
+}
+
+@inproceedings{ gustedt:parallel,
+ author = "Jens Gustedt",
+ title = "Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel",
+ booktitle = "Symposium on Theoretical Aspects of Computer Science",
+ pages = "421-431",
+ year = "1998",
+ url = "citeseer.ist.psu.edu/223918.html"
+}
+
+@article{ myrvold:rank,
+ title={{Ranking and unranking permutations in linear time}},
+ author={Myrvold, W.J. and Ruskey, F.},
+ journal={Information Processing Letters},
+ volume={79},
+ number={6},
+ pages={281--284},
+ year={2001}
+}
+
+@inproceedings{ critani:rau,
+ title={{Ranking and unranking permutations with applications}},
+ author={Critani, F. and Dall'Aglio, M. and Di Biase, G.},
+ booktitle={Innovation in Mathematics: Proceedings of Second International Mathematica Symposium},
+ pages = "99-106",
+ year = "1997"
+}
+
+@article{ ruskey:ham,
+ title={{The Hamiltonicity of directed-Cayley graphs (or: A tale of backtracking)}},
+ author={Ruskey, F. and Jiang, M. and Weston, A.},
+ journal={Discrete Appl. Math},
+ volume={57},
+ pages={75--83},
+ year={1995}
+}
+
+@article{ ruskey:hce,
+ title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn}},
+ author={Ruskey, F. and Savage, C.D.},
+ journal={SIAM Journal on Discrete Mathematics},
+ volume={6},
+ number={1},
+ pages={152--166},
+ year={1993}
+}
+
+@article{ liehe:raulow,
+ title={{Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis}},
+ author={Liebehenschel, J.},
+ journal={Journal of Automata, Languages and Combinatorics},
+ volume={2},
+ number={4},
+ pages={227--268},
+ year={1997}
+}
+
+@book{ reingold:catp,
+ title={{Combinatorial Algorithms: Theory and Practice}},
+ author={Reingold, E.M.},
+ year={1977},
+ publisher={Prentice Hall College Div}
+}
+
+@inproceedings{ dietz:oal,
+ author = {Paul F. Dietz},
+ title = {Optimal Algorithms for List Indexing and Subset Rank},
+ booktitle = {WADS '89: Proceedings of the Workshop on Algorithms and Data Structures},
+ year = {1989},
+ isbn = {3-540-51542-9},
+ pages = {39--46},
+ publisher = {Springer-Verlag},
+ address = {London, UK},
+}
+
+@book { ss:fifteen,
+ title={{The 15 Puzzle Book}},
+ author={Slocum, J. and Sonneveld D.},
+ year={2006},
+ publisher={The Slocum Puzzle Foundation, Beverly Hills, CA, USA}
+}
+
+@article{ rs:wagner,
+ title={{Graph minors: XX. Wagner's Conjecture}},
+ author={Robertson, N. and Seymour, P. D.},
+ journal={Journal of Combinatorial Theory Series B},
+ volume={92},
+ number={2},
+ pages={325--357},
+ year={2004},
+ publisher={Academic Press, Inc. Orlando, FL, USA}
+}
+
+@book{ matnes:idm,
+ title={{Invitation to Discrete Mathematics}},
+ author={Matou{\v{s}}ek, J. and Ne{\v{s}}et{\v{r}}il, J.},
+ year={1998},
+ publisher={Oxford University Press}
+}
+
+@article{ stanley:econe,
+ title={{Enumerative combinatorics. Vol. 1}},
+ author={Stanley, R.P.},
+ journal={Cambridge Studies in Advanced Mathematics},
+ volume={49},
+ year={1997}
+}
+
+@article{ kaplansky:rooks,
+ title={{The problem of the rooks and its applications}},
+ author={Kaplansky, I. and Riordan, J.},
+ journal={Duke Math. J},
+ volume={13},
+ number={2},
+ pages={259--268},
+ year={1946}
+}
+
+@article{ dinic:flow,
+ author = {E. A. Dinic},
+ title = {Algorithm for solution of a problem of maximum flow in networks with power estimation},
+ journal = {Soviet Math. Dokl.},
+ volume = {11},
+ year = {1970},
+ pages = {1277--1280}
+}
+
+@article{ even:dinic,
+ author = {Shimon Even and Robert Endre Tarjan},
+ title = {Network Flow and Testing Graph Connectivity},
+ publisher = {SIAM},
+ year = {1975},
+ journal = {SIAM Journal on Computing},
+ volume = {4},
+ number = {4},
+ pages = {507--518},
+ url = {http://link.aip.org/link/?SMJ/4/507/1},
+ doi = {10.1137/0204043}
+}
+
+@article{ valiant:permanent,
+ title={{The complexity of computing the permanent}},
+ author={Valiant, L. G.},
+ journal={Theoretical Computer Science},
+ volume={8},
+ number={2},
+ pages={189--201},
+ year={1979}
+}
+
+@article{ jerrum:permanent,
+ title={{A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries}},
+ author={Jerrum, M. and Sinclair, A. and Vigoda, E.},
+ journal={Journal of the ACM},
+ volume={51},
+ number={4},
+ pages={671--697},
+ year={2004}
+}
+
+@article{ kasteleyn:crystals,
+ title={{Graph theory and crystal physics}},
+ author={Kasteleyn, P. W.},
+ journal={Graph Theory and Theoretical Physics},
+ publisher={Academic Press, London},
+ pages={43--110},
+ year={1967}
+}
+
+@article{ yuster:matching,
+ title={{Maximum matching in graphs with an excluded minor}},
+ author={Yuster, R. and Zwick, U.},
+ journal={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
+ pages={108--117},
+ year={2007},
+ publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
+}
+
+@article{ mucha:matching,
+ title={{Maximum Matchings in Planar Graphs via Gaussian Elimination}},
+ author={Mucha, M. and Sankowski, P.},
+ journal={Algorithmica},
+ volume={45},
+ number={1},
+ pages={3--20},
+ year={2006},
+ publisher={Springer}
+}
+
+@article {lovasz:minors,
+ title={{Graph Minor Theory}},
+ author={Lov\'asz, L.},
+ journal={Bulletin of the American Mathematical Society},
+ volume={43},
+ number={1},
+ pages={75--86},
+ year={2005}
+}
+
+@article{ andersson:fusion,
+ title={{Fusion trees can be implemented with AC0 instructions only}},
+ author={Andersson, A. and Miltersen, P.B. and Thorup, M.},
+ journal={Theoretical Computer Science},
+ volume={215},
+ number={1-2},
+ pages={337--344},
+ year={1999},
+ publisher={Elsevier}
+}
+
+@article{ thorup:rampq,
+ title={{On RAM priority queues}},
+ author={THORUP, M.},
+ journal={SIAM journal on computing(Print)},
+ volume={30},
+ number={1},
+ pages={86--109},
+ year={2001},
+ publisher={Society for Industrial and Applied Mathematics}
+}
+
+@article{ thorup:pqsssp,
+ title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
+ author={Thorup, M.},
+ journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
+ pages={149--158},
+ year={2003},
+ publisher={ACM Press New York, NY, USA}
+}
+
+@article{ chazelle:mstapprox,
+ title={{Approximating the Minimum Spanning Tree Weight in Sublinear Time}},
+ author={Chazelle, B. and Rubinfeld, R. and Trevisan, L.},
+ journal={SIAM Journal on Computing},
+ volume={34},
+ pages={1370},
+ year={2005},
+ publisher={SIAM}
+}
+
+@inproceedings{ czumaj:metric,
+ author = {Artur Czumaj and Christian Sohler},
+ title = {Estimating the weight of metric minimum spanning trees in sublinear-time},
+ booktitle = {STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},
+ year = {2004},
+ isbn = {1-58113-852-0},
+ pages = {175--183},
+ location = {Chicago, IL, USA},
+ doi = {http://doi.acm.org/10.1145/1007352.1007386},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
+
+@inproceedings{ czumaj:euclidean,
+ author = {Artur Czumaj and Funda Erg\"{u}n and Lance Fortnow and Avner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler},
+ title = {Sublinear-time approximation of Euclidean minimum spanning tree},
+ booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
+ year = {2003},
+ isbn = {0-89871-538-5},
+ pages = {813--822},
+ location = {Baltimore, Maryland},
+ publisher = {Society for Industrial and Applied Mathematics},
+ address = {Philadelphia, PA, USA},
+}
+
+@book{ ieee:binfp,
+ author = {IEEE},
+ title = {IEEE Standard 754-1985 for Binary Floating-point Arithmetic},
+ year = {1985},
+ publisher = {IEEE}
+}
+
+@article{ dgoldberg:fp,
+ title={{What every computer scientist should know about floating-point arithmetic}},
+ author={Goldberg, D.},
+ journal={ACM Computing Surveys (CSUR)},
+ volume={23},
+ number={1},
+ pages={5--48},
+ year={1991},
+ publisher={ACM Press New York, NY, USA}
+}
+
+@article{ thorup:floatint,
+ title={{Floats, Integers, and Single Source Shortest Paths}},
+ author={Thorup, M.},
+ journal={Journal of Algorithms},
+ volume={35},
+ number={2},
+ pages={189--201},
+ year={2000},
+ publisher={Academic Press}
+}
+
+@article{ shamos:closest,
+ title={{Closest-point problems}},
+ author={Shamos, M. I. and Hoey, D.},
+ journal={Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science},
+ pages={151--162},
+ year={1975}
+}
+
+@article{ fortune:voronoi,
+ title={{A sweepline algorithm for Voronoi diagrams}},
+ author={Fortune, S.},
+ journal={Algorithmica},
+ volume={2},
+ number={1},
+ pages={153--174},
+ year={1987},
+ publisher={Springer}
+}
+
+@article{ zhou:nodel,
+ title={{Efficient minimum spanning tree construction without Delaunay triangulation}},
+ author={Zhou, H. and Shenoy, N. and Nicholls, W.},
+ journal={Information Processing Letters},
+ volume={81},
+ number={5},
+ pages={271--276},
+ year={2002},
+ publisher={Elsevier}
+}
+
+@techreport{ eppstein:spanning,
+ title={{Spanning Trees and Spanners}},
+ author={Eppstein, D.},
+ year={1996},
+ institution={Information and Computer Science, University of California, Irvine}
+}
+
+@article{ garey:steiner,
+ title={{The Complexity of Computing Steiner Minimal Trees}},
+ author={Garey, M.R. and Graham, R.L. and Johnson, D.S.},
+ journal={SIAM Journal on Applied Mathematics},
+ volume={32},
+ number={4},
+ pages={835--859},
+ year={1977},
+}
+
+@article{ garey:rectisteiner,
+ title={{The Rectilinear Steiner Tree Problem is NP-Complete}},
+ author={Garey, M.R. and Johnson, D.S.},
+ journal={SIAM Journal on Applied Mathematics},
+ volume={32},
+ number={4},
+ pages={826--834},
+ year={1977},
+}
+
+@article{ proemel:steiner,
+ title={{A new approximation algorithm for the Steiner tree problem with performance ratio $5/3$}},
+ author={Promel, H.J. and Steger, A.},
+ journal={Journal of Algorithms},
+ volume={36},
+ pages={89--101},
+ year={2000}
+}
+
+@article{ arora:tspapx,
+ title={{Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems}},
+ author={Arora, S.},
+ journal={Journal of the ACM (JACM)},
+ volume={45},
+ number={5},
+ pages={753--782},
+ year={1998},
+ publisher={ACM Press New York, NY, USA}
+}
+
+@article{ harel:nca,
+ title={{Fast algorithms for finding nearest common ancestors}},
+ author={Harel, D. and Tarjan, R.E.},
+ journal={SIAM Journal on Computing},
+ volume={13},
+ number={2},
+ pages={338--355},
+ year={1984},
+ publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
+}
+
+@article{ gomoryhu,
+ author = "R. E. Gomory and T. C. Hu",
+ title = "Multi-Terminal Network Flows",
+ journal = "{Journal of SIAM}",
+ volume = {9},
+ number = {4},
+ year = {1961},
+ pages = {551--570}
+}
+
+@inproceedings{ bhalgat:ght,
+ author = {Ramesh Hariharan and Telikepalli Kavitha and Debmalya Panigrahi and Anand Bhalgat},
+ title = {{An $\widehat\O(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs}},
+ booktitle = {STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing},
+ year = {2007},
+ isbn = {978-1-59593-631-8},
+ pages = {605--614},
+ location = {San Diego, California, USA},
+ doi = {http://doi.acm.org/10.1145/1250790.1250879},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
+
+@article{ sleator:trees,
+ title={{A data structure for dynamic trees}},
+ author={Sleator, D.D. and Tarjan, R.E.},
+ journal={Journal of Computer and System Sciences},
+ volume={26},
+ number={3},
+ pages={362--391},
+ year={1983},
+ publisher={Academic Press, Inc. Orlando, FL, USA}
+}
projects / saga.git / blobdiff