-@inproceedings{ bender00lca,
+@inproceedings{ bender:lca,
author = "Michael A. Bender and Martin Farach-Colton",
title = "The {LCA} Problem Revisited",
booktitle = "Latin American Theoretical {INformatics}",
publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co.}
}
-@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}
-}
-
@article{ graham:msthistory,
title={{On the history of the minimum spanning tree problem}},
author={Graham, R.L. and Hell, P.},
title = {Algorithm for solution of a problem of maximum flow in networks with power estimation},
journal = {Soviet Math. Dokl.},
volume = {11},
- year = {1980},
+ year = {1970},
pages = {1277--1280}
}
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