More verification.

[saga.git] / biblio.bib

diff --git a/biblio.bib b/biblio.bib
index b638f1b1ec15a7a5117095898016e82f300253a2..10335d477189d1202b194b9ef173da29808d203a 100644 (file)
--- a/biblio.bib
+++ b/biblio.bib
@@ -1,4 +1,4 @@
-@inproceedings{ bender00lca,
+@inproceedings{ bender:lca,
     author = "Michael A. Bender and Martin Farach-Colton",
     title = "The {LCA} Problem Revisited",
     booktitle = "Latin American Theoretical {INformatics}",
@@ -927,3 +927,154 @@ inproceedings{ pettie:minirand,
  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}
+}