year = "2000",
url = "citeseer.ist.psu.edu/bender00lca.html" }
-@inproceedings{ frederickson91ambivalent,
+@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},
+ volume={26},
+ number={2},
+ pages={484--538},
+ year={1997},
+ publisher={Society for Industrial and Applied Mathematics}
+}
+
+@inproceedings{ frederickson:ambifocs,
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",
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},
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}",
title={{Dynamick\'e grafov\'e algoritmy}},
author={Martin Mare\v{s}},
school={Charles University in Prague, Faculty of Math and Physics},
- year={2000}
+ year={2000},
+ notes={In Czech}
}
@techreport{ henzinger:twoec,
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}
+}
+
+@techreport { mm:ga,
+ author = "Martin Mare\v{s}",
+ title = "{Krajinou grafov\'ych algoritm\accent23u}",
+ institution = "Institut Teoretick\'e Informatiky",
+ address = "Praha, Czech Republic",
+ year = "2007",
+ number = "2007--330",
+ type = "ITI series",
+ note = {In Czech},
+}
+
+@book { horak:mofivefour,
+ author = {Hor\'ak, Karel and Mare\v{s}, Martin and Novotn\'y, Peter and \v{S}im\v{s}a, Jarom\'\i{}r and \v{S}vr\v{c}ek, Jaroslav and T\"opfer, Pavel and Zhouf, Jaroslav},
+ title = {54.~ro\v{c}n\'\i{}k matematick\'e olympi\'ady na st\v{r}edn\'\i{}ch \v{s}kol\'ach},
+ publisher = {Jednota \v{c}esk\'ych matematik\accent23u a fyzik\accent23u},
+ address = {Praha},
+ year = {2007},
+ note = {In Czech},
+ isbn = {80-7015-109-9},
+}
projects / saga.git / blobdiff