Practical and parallel algorithms.

[saga.git] / biblio.bib

diff --git a/biblio.bib b/biblio.bib
index 2edd9d2ef6c1b61cdbd04b3283f79c366c519f34..9e569206053bf899d33eb3ed3e4cd7fedb42ac4f 100644 (file)
--- a/biblio.bib
+++ b/biblio.bib
@@ -14,7 +14,7 @@
     year = "1991",
     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},
@@ -28,6 +28,17 @@
  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},
+  publisher={ACM Press New York, NY, USA}
+}
+
 @inproceedings { fw:transdich,
    author = "M. Fredman and D. E. Willard",
    title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}",
@@ -1397,3 +1408,142 @@
   year={1981},
   publisher={SIAM}
 }
+
+@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},
+ year = {2000},
+ isbn = {1-58113-184-4},
+ pages = {343--350},
+ location = {Portland, Oregon, United States},
+ doi = {http://doi.acm.org/10.1145/335305.335345},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+}
+
+@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},
+  publisher={Springer}
+}
+
+@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},
+  publisher = {Academic Press, Inc.},
+  address = {Orlando, FL, USA},
+}
+
+@inproceedings{ hagerup:sssp,
+  author = {Torben Hagerup},
+  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,
+    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},
+  publisher = {SIAM},
+  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},
+  publisher = {ACM},
+  address = {New York, NY, USA},
+}
+
+@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},
+  publisher={Springer}
+}
+
+@article{ pettie:pairing,
+  author = {Seth Pettie},
+  title = {Towards a Final Analysis of Pairing Heaps},
+  journal = {focs},
+  volume = {00},
+  year = {2005},
+  isbn = {0-7695-2468-0},
+  pages = {174-183},
+  doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.75},
+  publisher = {IEEE Computer Society},
+  address = {Los Alamitos, CA, USA},
+}
+
+@book{ jaja:parallel,
+  title={{An introduction to parallel algorithms}},
+  author={J{\'a}J{\'a}, J.},
+  year={1992},
+  publisher={Addison Wesley Longman Publishing Co., Inc. Redwood City, CA, USA}
+}