]> mj.ucw.cz Git - saga.git/blob - biblio.bib
Finish PM.
[saga.git] / biblio.bib
1 @inproceedings{ bender00lca,
2     author = "Michael A. Bender and Martin Farach-Colton",
3     title = "The {LCA} Problem Revisited",
4     booktitle = "Latin American Theoretical {INformatics}",
5     pages = "88-94",
6     year = "2000",
7     url = "citeseer.ist.psu.edu/bender00lca.html" }
8
9 @inproceedings{ frederickson91ambivalent,
10     author = "Greg N. Frederickson",
11     title = "Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and $k$ Smallest Spanning Trees",
12     booktitle = "{IEEE} Symposium on Foundations of Computer Science",
13     pages = "632-641",
14     year = "1991",
15     url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" }
16
17 @article{ tarjan:setunion,
18  author = {Robert E. Tarjan and Jan van Leeuwen},
19  title = {Worst-case Analysis of Set Union Algorithms},
20  journal = {J. ACM},
21  volume = {31},
22  number = {2},
23  year = {1984},
24  issn = {0004-5411},
25  pages = {245--281},
26  doi = {http://doi.acm.org/10.1145/62.2160},
27  publisher = {ACM Press},
28  address = {New York, NY, USA},
29 }
30
31 @inproceedings { fw:transdich,
32    author = "M. Fredman and D. E. Willard",
33    title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}",
34    booktitle = "{Proceedings of FOCS'90}",
35    pages = "719--725",
36    year = "1990"
37 }
38
39 @article{boas77,
40   author    = {Peter van Emde Boas},
41   title     = {Preserving Order in a Forest in Less Than Logarithmic Time
42                and Linear Space.},
43   journal   = {Inf. Process. Lett.},
44   volume    = {6},
45   number    = {3},
46   year      = {1977},
47   pages     = {80-82},
48   bibsource = {DBLP, http://dblp.uni-trier.de}
49 }
50
51 @inproceedings{ thorup:aczero,
52  author = {Mikkel Thorup},
53  title = {On AC0 implementations of fusion trees and atomic heaps},
54  booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
55  year = {2003},
56  isbn = {0-89871-538-5},
57  pages = {699--707},
58  location = {Baltimore, Maryland},
59  publisher = {Society for Industrial and Applied Mathematics},
60  address = {Philadelphia, PA, USA},
61  }
62
63 @article{ benamram:pm,
64     author = "Ben-Amram, Amir M.",
65     title = "What is a ``Pointer Machine''?",
66     journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
67     volume = "26",
68     year = "1995",
69     url = "citeseer.ist.psu.edu/ben-amram95what.html" }
70
71 @article{ matsui:planar,
72     author = "Tomomi Matsui",
73     title = "{The Minimum Spanning tree Problem on a Planar Graph}",
74     journal = "Discrete Applied Mathematics",
75     volume = "58",
76     year = "1995",
77     pages = "91--94",
78     url = "citeseer.nj.nec.com/2319.html"
79 }
80
81 @article{ chazelle:ackermann,
82     author = "Bernard Chazelle",
83     title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
84     journal = jacm,
85     volume = "47",
86     pages = "1028--1047",
87     year = "2000"
88 }
89
90 @article{ nesetril:history,
91     author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
92     title = "{Some remarks on the history of MST-problem}",
93     journal = "Archivum Mathematicum",
94     volume = "33",
95     pages = "15--22",
96     year = "1997"
97 }
98
99 @article{ nesetril:boruvka,
100     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
101     title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
102     journal = "Discrete Mathematics",
103     volume = "233(1--3)",
104     pages = "3--36",
105     year = "2001"
106 }
107
108 @incollection { nesetril:minors,
109     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
110     title = "{Colorings and Homomorphisms of Minor Closed Classes}",
111     booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
112     editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
113     year = "2003",
114     pages = "651--664",
115     publisher = "Springer Verlag"
116 }
117
118 @article { boruvka:ojistem,
119     author = "Otakar Bor{\accent23u}vka",
120     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
121     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
122     volume = "III",
123     year = "1926",
124     pages = "37--58",
125     note = "Czech with German summary"
126 }
127
128 @article { boruvka:networks,
129     author = "Otakar Bor{\accent23u}vka",
130     title = "{P\v{r}\'\i{}sp\v{e}vek k~\v{r}e\v{s}en\'\i{} ot\'azky ekonomick\'e stavby elektrovodn\'y{}ch s\'\i{}t\'\i{} (Contribution to the solution of a problem of economical construction of electric networks)}",
131     journal = "Elektronick\'y obzor",
132     volume = "15",
133     year = "1926",
134     pages = "153--154",
135     note = "Czech"
136 }
137
138 @article { jarnik:ojistem,
139     author = "Vojt\v{e}ch Jarn\'\i{}k",
140     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
141     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
142     volume = "VI",
143     year = "1930",
144     pages = "57--63",
145     note = "Czech"
146 }
147
148 @book { tarjan:dsna,
149     author = "Robert E. Tarjan",
150     title = "{Data structures and network algorithms}",
151     series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}",
152     volume = 44,
153     year = "1983",
154     publisher = "SIAM"
155 }
156
157 @article { gh:history,
158     author = "R. L. Graham and P. Hell",
159     title = "{On the history of the minimum spanning tree problem}",
160     journal = "{Annals of the History of Computing}",
161     volume = "7",
162     year = "1985",
163     pages = "43--57"
164 }
165
166 @techreport { pettie:ackermann,
167     author = "Seth Pettie",
168     title = "{Finding minimum spanning trees in $O(m\alpha(m,n))$ time}",
169     institution = "Univ. of Texas at Austin",
170     year = "1999",
171     number = "TR99-23",
172     type = "Tech Report"
173 }
174
175 @inproceedings { pettie:optimal,
176    author = "Seth Pettie and Vijaya Ramachandran",
177    title = "{An Optimal Minimum Spanning Tree Algorithm}",
178    booktitle = "{Proceedings of ICALP'2000}",
179    year = "2000",
180    publisher = "Springer Verlag",
181    pages = "49--60"
182 }
183
184 @article { pettie:alpha,
185   title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}},
186   author={Pettie, S.},
187   year={1999},
188   publisher={University of Texas at Austin Austin, TX, USA}
189 }
190
191 @article { karger:randomized,
192    author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
193    title = "{Linear expected-time algorithms for connectivity problems}",
194    journal = jacm,
195    volume = "42",
196    pages = "321--328",
197    year = "1995"
198 }
199
200 @article { frederickson:online,
201    author = "Greg N. Frederickson",
202    title = "{Data structures for on-line updating of minimum spanning trees}",
203    journal = "{SIAM Journal on Computing}",
204    volume = "14",
205    pages = "781--798",
206    year = "1985"
207 }
208
209 @article { mm:mst,
210    author = "Martin Mare\v{s}",
211    title = "{Two linear time algorithms for MST on minor closed graph classes}",
212    journal = "{Archivum Mathematicum}",
213    volume = "40",
214    pages = "315--320",
215    year = "2004"
216 }
217
218 @article{ ft:fibonacci,
219  author = {Michael L. Fredman and Robert Endre Tarjan},
220  title = {Fibonacci heaps and their uses in improved network optimization algorithms},
221  journal = {J. ACM},
222  volume = {34},
223  number = {3},
224  year = {1987},
225  issn = {0004-5411},
226  pages = {596--615},
227  doi = {http://doi.acm.org/10.1145/28869.28874},
228  publisher = {ACM Press},
229  address = {New York, NY, USA},
230  }
231
232 @article{ komlos:verify,
233   author    = {J{\'a}nos Koml{\'o}s},
234   title     = {Linear verification for spanning trees.},
235   journal   = {Combinatorica},
236   volume    = {5},
237   number    = {1},
238   year      = {1985},
239   pages     = {57--65},
240   bibsource = {DBLP, http://dblp.uni-trier.de}
241 }
242
243 @inproceedings{ king:verify,
244     author = "Valerie King",
245     title = "A Simpler Minimum Spanning Tree Verification Algorithm",
246     booktitle = "Workshop on Algorithms and Data Structures",
247     pages = "440--448",
248     year = "1995",
249     url = "citeseer.ist.psu.edu/king95simpler.html" }
250
251 @article{ king:verifytwo,
252   title={{A Simpler Minimum Spanning Tree Verification Algorithm}},
253   author={King, Valerie},
254   journal={Algorithmica},
255   volume={18},
256   pages={263--270},
257   year={1997}
258 }
259
260 @book { schrijver,
261     author = "Alexander Schrijver",
262     title = "{Combinatorial Optimization --- Polyhedra and Efficiency}",
263     series = "Algorithms and Combinatorics",
264     volume = 24,
265     year = 2003,
266     publisher = "Springer Verlag"
267 }
268
269 @inproceedings{ thorup:ac0,
270  author = {Mikkel Thorup},
271  title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
272  booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
273  year = {2003},
274  isbn = {0-89871-538-5},
275  pages = {699--707},
276  location = {Baltimore, Maryland},
277  publisher = {Society for Industrial and Applied Mathematics},
278  address = {Philadelphia, PA, USA},
279 }
280
281 @article{ kruskal:mst,
282   title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
283   author={Kruskal Jr, J.B.},
284   journal={Proceedings of the American Mathematical Society},
285   volume={7},
286   number={1},
287   pages={48--50},
288   year={1956},
289   publisher={JSTOR}
290 }
291
292 @book{ diestel:gt,
293   title={{Graph Theory}},
294   author={Diestel, R.},
295   year={2005},
296   publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K}
297 }
298
299 @article{ thorup:pq,
300   title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
301   author={Thorup, M.},
302   journal={Proceedings of the thirty-fifth ACM symposium on Theory of computing},
303   pages={149--158},
304   year={2003},
305   publisher={ACM Press New York, NY, USA}
306 }
307
308 @article{ graham:msthistory,
309   title={{On the history of the minimum spanning tree problem}},
310   author={Graham, R.L. and Hell, P.},
311   journal={Annals of the History of Computing},
312   volume={7},
313   number={1},
314   pages={43--57},
315   year={1985}
316 }
317
318 @article{ cayley:trees,
319   title={{A theorem on trees}},
320   author={Cayley, Arthur},
321   journal={Quart. J. Math},
322   volume={23},
323   year={1889},
324   pages={376--378}
325 }
326
327 @article{ dijkstra:mst,
328   title={{A note on two problems in connexion with graphs}},
329   author = "Dijkstra, E. W.",
330   journal={Numerische Mathematik},
331   volume={1},
332   number={1},
333   pages={269--271},
334   year={1959},
335   publisher={Springer}
336 }
337
338 @article{ prim:mst,
339   author = "Prim, R. C.",
340   title = "Shortest connection networks and some generalizations",
341   journal = "Bell System Technical Journal",
342   volume = "36",
343   year = "1957",
344   pages={567--574},
345 }
346
347 @article{ choquet:mst,
348   title={{Etude de certains r{\'e}seaux de routes (in French)}},
349   author={Choquet, Gustave},
350   journal={Comptes-rendus de l'Académie des Sciences},
351   volume={206},
352   pages={310},
353   year={1938}
354 }
355
356 @incollection { sollin:mst,
357   title={{Le trace de canalisation (in French)}},
358   author={Sollin, M.},
359   booktitle={Programming, Games, and Transportation Networks},
360   editor={Berge, C. and Ghouilla-Houri, A.},
361   publisher={Wiley, New York},
362   year={1965}
363 }
364
365 @article{ boyer:cutting,
366   title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
367   author={Boyer, J.M. and Myrvold, W.J.},
368   journal={Journal of Graph Algorithms and Applications},
369   volume={8},
370   number={3},
371   pages={241--273},
372   year={2004}
373 }
374
375 @inproceedings{ takaoka:twothree,
376   title={{Theory of 2-3 Heaps}},
377   author={Takaoka, T. and Christchurch, N. Z.},
378   booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON'99},
379   location={Tokyo, Japan},
380   year={1999},
381   pages={41--50},
382   publisher={Springer},
383   series={{Lecture Notes in Computer Science}},
384   volume={1627}
385 }
386
387 @inproceedings{ takaoka:trinomial,
388   title={{Theory of Trinomial Heaps}},
389   author={Takaoka, Tadao},
390   booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
391   location={Sydney, Australia},
392   year={2000},
393   pages={362--372},
394   publisher={Springer},
395   series={{Lecture Notes in Computer Science}},
396   volume={1858}
397 }
398
399 @book{ clrs,
400   title={{Introduction to Algorithms}},
401   author={Leiserson, C.E. and Rivest, R.L. and Cormen, T.H. and Stein, C.},
402   year={2001},
403   publisher={McGraw-Hill}
404 }
405
406 @inproceedings{ pettie:onlineverify,
407   author = "S. Pettie",
408   title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
409     tree verification problem",
410   booktitle = "Proc. 43rd Annual Symp. on the Foundations of Computer Science, Vancouver, Canada",
411   year = "2002",
412   url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
413 }
414
415 @article{ dixon:verify,
416     author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
417     title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
418     journal = "SIAM J. Comput.",
419     volume = "21",
420     number = "6",
421     pages = "1184-1192",
422     year = "1992",
423     url = "citeseer.ist.psu.edu/dixon92verification.html"
424 }
425
426 inproceedings{ pettie:minirand,
427  author = {Seth Pettie and Vijaya Ramachandran},
428  title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
429  booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms},
430  year = {2002},
431  isbn = {0-89871-513-X},
432  pages = {713--722},
433  location = {San Francisco, California},
434  publisher = {Society for Industrial and Applied Mathematics},
435  address = {Philadelphia, PA, USA}
436 }
437
438 @article{ buchsbaum:verify,
439   title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
440   author={Buchsbaum, A.L. and Kaplan, H. and Rogers, A. and Westbrook, J.R.},
441   journal={Proceedings of the thirtieth annual ACM symposium on Theory of computing},
442   pages={279--288},
443   year={1998},
444   publisher={ACM Press New York, NY, USA}
445 }
446
447 @article{ bacala:parametric,
448   title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
449   author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
450   journal={Theoretical Computer Science},
451   volume={181},
452   number={1},
453   pages={57--74},
454   year={1997},
455   publisher={Elsevier}
456 }
457
458 @inproceedings{ katriel:cycle,
459   author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
460   title = "A practical minimum spanning tree algorithm using the cycle property",
461   booktitle = "11th European Symposium on Algorithms(ESA)",
462   number = "2832",
463   series = "LNCS",
464   pages = "679--690",
465   publisher = "Springer",
466   year = "2003",
467   url = "citeseer.ist.psu.edu/katriel03practical.html"
468 }
469
470 @article{ alstrup:nca,
471   title={{Nearest common ancestors: a survey and a new distributed algorithm}},
472   author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
473   journal={Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures},
474   pages={258--264},
475   year={2002},
476   publisher={ACM Press New York, NY, USA}
477 }
478
479 @article{ gabow:mst,
480   title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
481   author={Gabow, H.N. and Galil, Z. and Spencer, T. and Tarjan, R.E.},
482   journal={Combinatorica},
483   volume={6},
484   number={2},
485   pages={109--122},
486   year={1986},
487   publisher={Springer}
488 }
489
490 @Unpublished{ eisner:tutorial,
491   author =       {Jason Eisner},
492   title =        {State-of-the-Art Algorithms for Minimum Spanning
493                   Trees: A Tutorial Discussion},
494   note =         {Manuscript available online (78 pages), University of Pennsylvania}, 
495   year =         1997,
496   url =          {http://cs.jhu.edu/~jason/papers/#ms97},
497 }
498
499 @article{ aho:lca,
500   title={{On finding lowest common ancestors in trees.}},
501   author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
502   journal={SIAM Journal on Computing},
503   volume={5},
504   pages={115--132},
505   year={1976}
506 }
507
508 @book{ knuth:fundalg,
509  author = {Donald E. Knuth},
510  title = {The art of computer programming, volume 1 (3rd ed.): fundamental algorithms},
511  year = {1997},
512  isbn = {0-201-89683-4},
513  publisher = {Addison Wesley Longman Publishing Co., Inc.},
514  address = {Redwood City, CA, USA},
515 }
516
517 @inproceedings{ hagerup:wordram,
518  author = {Torben Hagerup},
519  title = {{Sorting and Searching on the Word RAM}},
520  booktitle = {STACS '98: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science},
521  year = {1998},
522  isbn = {3-540-64230-7},
523  pages = {366--398},
524  publisher = {Springer-Verlag},
525  address = {London, UK},
526 }
527
528 @inproceedings{ cook:ram,
529  author = {Stephen A. Cook and Robert A. Reckhow},
530  title = {Time-bounded random access machines},
531  booktitle = {STOC '72: Proceedings of the fourth annual ACM symposium on Theory of computing},
532  year = {1972},
533  pages = {73--80},
534  location = {Denver, Colorado, United States},
535  doi = {http://doi.acm.org/10.1145/800152.804898},
536  publisher = {ACM},
537  address = {New York, NY, USA},
538 }
539
540 @book{ okasaki:funcds,
541   author = {Chris Okasaki},
542   title = {Purely Functional Data Structures},
543   year = {1999},
544   publisher = {Cambridge University Press}
545 }
546
547 @book { intel:pentium,
548   author = {{Intel Corp.}},
549   title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference},
550   year = {2007},
551   publisher = {Intel Corp.},
552   xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
553 }