]> mj.ucw.cz Git - saga.git/blob - biblio.bib
Special cases.
[saga.git] / biblio.bib
1 @inproceedings{ bender:lca,
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{ boas:vebt,
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 @article{ benamram:pm,
52     author = "Ben-Amram, Amir M.",
53     title = "What is a ``Pointer Machine''?",
54     journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)",
55     volume = "26",
56     year = "1995",
57     url = "citeseer.ist.psu.edu/ben-amram95what.html" }
58
59 @article{ matsui:planar,
60     author = "Tomomi Matsui",
61     title = "{The Minimum Spanning tree Problem on a Planar Graph}",
62     journal = "Discrete Applied Mathematics",
63     volume = "58",
64     year = "1995",
65     pages = "91--94",
66     url = "citeseer.nj.nec.com/2319.html"
67 }
68
69 @article{ chazelle:ackermann,
70     author = "Bernard Chazelle",
71     title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}",
72     journal = jacm,
73     volume = "47",
74     pages = "1028--1047",
75     year = "2000"
76 }
77
78 @article{ nesetril:history,
79     author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
80     title = "{Some remarks on the history of MST-problem}",
81     journal = "Archivum Mathematicum",
82     volume = "33",
83     pages = "15--22",
84     year = "1997"
85 }
86
87 @article{ nesetril:boruvka,
88     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}",
89     title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}",
90     journal = "Discrete Mathematics",
91     volume = "233(1--3)",
92     pages = "3--36",
93     year = "2001"
94 }
95
96 @incollection { nesetril:minors,
97     author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez",
98     title = "{Colorings and Homomorphisms of Minor Closed Classes}",
99     booktitle = "Discrete and Computational Geometry: The Goodman-Pollack Festschrift",
100     editor = "B. Aronov and S. Basu and J. Pach and M. Sharir",
101     year = "2003",
102     pages = "651--664",
103     publisher = "Springer Verlag"
104 }
105
106 @article { boruvka:ojistem,
107     author = "Otakar Bor{\accent23u}vka",
108     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
109     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
110     volume = "III",
111     year = "1926",
112     pages = "37--58",
113     note = "Czech with German summary"
114 }
115
116 @article { boruvka:networks,
117     author = "Otakar Bor{\accent23u}vka",
118     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)}",
119     journal = "Elektronick\'y obzor",
120     volume = "15",
121     year = "1926",
122     pages = "153--154",
123     note = "Czech"
124 }
125
126 @article { jarnik:ojistem,
127     author = "Vojt\v{e}ch Jarn\'\i{}k",
128     title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}",
129     journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}",
130     volume = "VI",
131     year = "1930",
132     pages = "57--63",
133     note = "Czech"
134 }
135
136 @book { tarjan:dsna,
137     author = "Robert E. Tarjan",
138     title = "{Data structures and network algorithms}",
139     series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}",
140     volume = 44,
141     year = "1983",
142     publisher = "SIAM"
143 }
144
145 @article { gh:history,
146     author = "R. L. Graham and P. Hell",
147     title = "{On the history of the minimum spanning tree problem}",
148     journal = "{Annals of the History of Computing}",
149     volume = "7",
150     year = "1985",
151     pages = "43--57"
152 }
153
154 @techreport { pettie:ackermann,
155     author = "Seth Pettie",
156     title = "{Finding minimum spanning trees in $\O(m\alpha(m,n))$ time}",
157     institution = "Univ. of Texas at Austin",
158     year = "1999",
159     number = "TR99-23",
160     type = "Tech Report"
161 }
162
163 @inproceedings { pettie:optimal,
164    author = "Seth Pettie and Vijaya Ramachandran",
165    title = "{An Optimal Minimum Spanning Tree Algorithm}",
166    booktitle = "{Proceedings of ICALP'2000}",
167    year = "2000",
168    publisher = "Springer Verlag",
169    pages = "49--60"
170 }
171
172 @article { pettie:alpha,
173   title={{Finding Minimum Spanning Trees in $\O(m\acker(m,n))$ Time}},
174   author={Pettie, S.},
175   year={1999},
176   publisher={University of Texas at Austin Austin, TX, USA}
177 }
178
179 @article { karger:randomized,
180    author = "D. R. Karger and P. N. Klein and R. E. Tarjan",
181    title = "{Linear expected-time algorithms for connectivity problems}",
182    journal = jacm,
183    volume = "42",
184    pages = "321--328",
185    year = "1995"
186 }
187
188 @article { frederickson:online,
189    author = "Greg N. Frederickson",
190    title = "{Data structures for on-line updating of minimum spanning trees}",
191    journal = "{SIAM Journal on Computing}",
192    volume = "14",
193    pages = "781--798",
194    year = "1985"
195 }
196
197 @article { mm:mst,
198    author = "Martin Mare\v{s}",
199    title = "{Two linear time algorithms for MST on minor closed graph classes}",
200    journal = "{Archivum Mathematicum}",
201    volume = "40",
202    pages = "315--320",
203    year = "2004"
204 }
205
206 @inproceedings{ mm:rank,
207   author = "Martin Mare\v{s} and Milan Straka",
208   title = "Linear-Time Ranking of Permutations",
209   booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium",
210   location = "Eilat, Israel, October 8--10, 2007",
211   volume = "4698",
212   series = "Lecture Notes in Computer Science",
213   pages = "187--193",
214   publisher = "Springer",
215   year = "2007",
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:aczero,
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.}
297 }
298
299 @article{ graham:msthistory,
300   title={{On the history of the minimum spanning tree problem}},
301   author={Graham, R.L. and Hell, P.},
302   journal={Annals of the History of Computing},
303   volume={7},
304   number={1},
305   pages={43--57},
306   year={1985}
307 }
308
309 @article{ cayley:trees,
310   title={{A theorem on trees}},
311   author={Cayley, Arthur},
312   journal={Quart. J. Math},
313   volume={23},
314   year={1889},
315   pages={376--378}
316 }
317
318 @article{ dijkstra:mst,
319   title={{A note on two problems in connexion with graphs}},
320   author = "Dijkstra, E. W.",
321   journal={Numerische Mathematik},
322   volume={1},
323   number={1},
324   pages={269--271},
325   year={1959},
326   publisher={Springer}
327 }
328
329 @article{ prim:mst,
330   author = "Prim, R. C.",
331   title = "Shortest connection networks and some generalizations",
332   journal = "Bell System Technical Journal",
333   volume = "36",
334   year = "1957",
335   pages={567--574},
336 }
337
338 @article{ choquet:mst,
339   title={{Etude de certains r{\'e}seaux de routes}},
340   author={Choquet, Gustave},
341   journal={Comptes-rendus de l'Académie des Sciences},
342   volume={206},
343   pages={310},
344   year={1938},
345   note={French}
346 }
347
348 @incollection { sollin:mst,
349   title={{Le trace de canalisation}},
350   author={Sollin, M.},
351   booktitle={Programming, Games, and Transportation Networks},
352   editor={Berge, C. and Ghouilla-Houri, A.},
353   publisher={Wiley, New York},
354   year={1965},
355   note={French}
356 }
357
358 @article{ boyer:cutting,
359   title={{On the cutting edge: Simplified $\O(n)$ planarity by edge addition}},
360   author={Boyer, J.M. and Myrvold, W.J.},
361   journal={Journal of Graph Algorithms and Applications},
362   volume={8},
363   number={3},
364   pages={241--273},
365   year={2004}
366 }
367
368 @inproceedings{ takaoka:twothree,
369   title={{Theory of 2-3 Heaps}},
370   author={Takaoka, T. and Christchurch, N. Z.},
371   booktitle={Computing and Combinatorics: 5th Annual International Conference, COCOON'99},
372   location={Tokyo, Japan},
373   year={1999},
374   pages={41--50},
375   publisher={Springer},
376   series={{Lecture Notes in Computer Science}},
377   volume={1627}
378 }
379
380 @inproceedings{ takaoka:trinomial,
381   title={{Theory of Trinomial Heaps}},
382   author={Takaoka, Tadao},
383   booktitle={Computing and Combinatorics: 6th Annual International Conference, COCOON 2000},
384   location={Sydney, Australia},
385   year={2000},
386   pages={362--372},
387   publisher={Springer},
388   series={{Lecture Notes in Computer Science}},
389   volume={1858}
390 }
391
392 @book{ clrs,
393   title={{Introduction to Algorithms}},
394   author={Leiserson, C.E. and Rivest, R.L. and Cormen, T.H. and Stein, C.},
395   year={2001},
396   publisher={McGraw-Hill}
397 }
398
399 @inproceedings{ pettie:onlineverify,
400   author = "S. Pettie",
401   title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
402     tree verification problem",
403   booktitle = "Proc. 43rd Annual Symp. on the Foundations of Computer Science, Vancouver, Canada",
404   year = "2002",
405   url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
406 }
407
408 @article{ dixon:verify,
409     author = "Brandon Dixon and Monika Rauch and Robert Endre Tarjan",
410     title = "Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time",
411     journal = "SIAM J. Comput.",
412     volume = "21",
413     number = "6",
414     pages = "1184-1192",
415     year = "1992",
416     url = "citeseer.ist.psu.edu/dixon92verification.html"
417 }
418
419 inproceedings{ pettie:minirand,
420  author = {Seth Pettie and Vijaya Ramachandran},
421  title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
422  booktitle = {SODA '02: Proceedings of the thirteenth annual ACM-SIAM Symposium on Discrete Algorithms},
423  year = {2002},
424  isbn = {0-89871-513-X},
425  pages = {713--722},
426  location = {San Francisco, California},
427  publisher = {Society for Industrial and Applied Mathematics},
428  address = {Philadelphia, PA, USA}
429 }
430
431 @article{ buchsbaum:verify,
432   title={{Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators}},
433   author={Buchsbaum, A.L. and Kaplan, H. and Rogers, A. and Westbrook, J.R.},
434   journal={Proceedings of the thirtieth annual ACM Symposium on Theory of Computing},
435   pages={279--288},
436   year={1998},
437   publisher={ACM Press New York, NY, USA}
438 }
439
440 @article{ bacala:parametric,
441   title={{Linear-time algorithms for parametric minimum spanning tree problems on planar graphs}},
442   author={Fern{\'a}ndez-Baca, D. and Slutzki, G.},
443   journal={Theoretical Computer Science},
444   volume={181},
445   number={1},
446   pages={57--74},
447   year={1997},
448   publisher={Elsevier}
449 }
450
451 @inproceedings{ katriel:cycle,
452   author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
453   title = "A practical minimum spanning tree algorithm using the cycle property",
454   booktitle = "11th European Symposium on Algorithms (ESA)",
455   number = "2832",
456   series = "LNCS",
457   pages = "679--690",
458   publisher = "Springer",
459   year = "2003",
460   url = "citeseer.ist.psu.edu/katriel03practical.html"
461 }
462
463 @article{ alstrup:nca,
464   title={{Nearest common ancestors: a survey and a new distributed algorithm}},
465   author={Alstrup, S. and Gavoille, C. and Kaplan, H. and Rauhe, T.},
466   journal={Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures},
467   pages={258--264},
468   year={2002},
469   publisher={ACM Press New York, NY, USA}
470 }
471
472 @article{ gabow:mst,
473   title={{Efficient algorithms for finding minimum spanning trees in undirected and directed graphs}},
474   author={Gabow, H.N. and Galil, Z. and Spencer, T. and Tarjan, R.E.},
475   journal={Combinatorica},
476   volume={6},
477   number={2},
478   pages={109--122},
479   year={1986},
480   publisher={Springer}
481 }
482
483 @Unpublished{ eisner:tutorial,
484   author =       {Jason Eisner},
485   title =        {State-of-the-Art Algorithms for Minimum Spanning
486                   Trees: A Tutorial Discussion},
487   note =         {Manuscript available online (78 pages), University of Pennsylvania}, 
488   year =         1997,
489   url =          {http://cs.jhu.edu/~jason/papers/#ms97},
490 }
491
492 @article{ aho:lca,
493   title={{On finding lowest common ancestors in trees.}},
494   author={Aho, A. V. and Hopcroft, J. E. and Ullman, J. D.},
495   journal={SIAM Journal on Computing},
496   volume={5},
497   pages={115--132},
498   year={1976}
499 }
500
501 @book{ knuth:fundalg,
502  author = {Donald E. Knuth},
503  title = {The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms},
504  year = {1997},
505  isbn = {0-201-89683-4},
506  publisher = {Addison Wesley Longman Publishing Co., Inc.},
507  address = {Redwood City, CA, USA},
508 }
509
510 @book{ knuth:seminalg,
511  author = {Donald E. Knuth},
512  title = {The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical algorithms},
513  year = {1997},
514  isbn = {978-0-201-89684-8},
515  publisher = {Addison Wesley Longman Publishing Co., Inc.},
516  address = {Redwood City, CA, USA},
517 }
518
519 @book{ knuth:sas,
520   author = {Donald E. Knuth},
521   title = {{The Art of Computer Programming, Volume 3 (2nd ed.): Sorting and Searching}},
522   year = {1998},
523   isbn = {978-0-201-89685-5},
524   publisher = {Addison Wesley Longman Publishing Co., Inc.},
525   address = {Redwood City, CA, USA},
526 }
527
528 @inproceedings{ hagerup:wordram,
529  author = {Torben Hagerup},
530  title = {{Sorting and Searching on the Word RAM}},
531  booktitle = {STACS '98: Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science},
532  year = {1998},
533  isbn = {3-540-64230-7},
534  pages = {366--398},
535  publisher = {Springer-Verlag},
536  address = {London, UK},
537 }
538
539 @inproceedings{ cook:ram,
540  author = {Stephen A. Cook and Robert A. Reckhow},
541  title = {Time-bounded random access machines},
542  booktitle = {STOC '72: Proceedings of the fourth annual ACM Symposium on Theory of Computing},
543  year = {1972},
544  pages = {73--80},
545  location = {Denver, Colorado, United States},
546  doi = {http://doi.acm.org/10.1145/800152.804898},
547  publisher = {ACM},
548  address = {New York, NY, USA},
549 }
550
551 @book{ okasaki:funcds,
552   author = {Chris Okasaki},
553   title = {Purely Functional Data Structures},
554   year = {1999},
555   publisher = {Cambridge University Press}
556 }
557
558 @book { intel:pentium,
559   author = {{Intel Corp.}},
560   title = {Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 2: Instruction Set Reference},
561   year = {2007},
562   publisher = {Intel Corp.},
563   xxx = {available online at http://www.intel.com/products/processor/manuals/index.htm}
564 }
565
566 @article{ hagerup:dd,
567   title={{Deterministic Dictionaries}},
568   author={Hagerup, T. and Miltersen, P.B. and Pagh, R.},
569   journal={J. Algorithms},
570   volume={41},
571   number={1},
572   pages={69--85},
573   year={2001}
574 }
575
576 @article{ fredman:sst,
577   title={{Storing a Sparse Table with $\O(1)$ Worst Case Access Time}},
578   author={Fredman, M.L. and Koml{\'o}s, J. and Szemer{\'e}di, E.},
579   journal={Journal of the ACM (JACM)},
580   volume={31},
581   number={3},
582   pages={538--544},
583   year={1984},
584   publisher={ACM Press New York, NY, USA}
585 }
586
587 @book{ motwani:randalg,
588   title={{Randomized Algorithms}},
589   author={Motwani, R. and Raghavan, P.},
590   year={1995},
591   publisher={Cambridge University Press}
592 }
593
594 @article{ fw:fusion,
595   title={{Surpassing the information theoretic bound with fusion trees}},
596   author={Fredman, M.L. and Willard, D.E.},
597   journal={Journal of Computer and System Sciences},
598   volume={47},
599   number={3},
600   pages={424--436},
601   year={1993},
602   publisher={Academic Press, Inc. Orlando, FL, USA}
603 }
604
605 @article{ han:detsort,
606   title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}},
607   author={Han, Y.},
608   journal={Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing},
609   pages={602--608},
610   year={2002},
611   publisher={ACM Press New York, NY, USA}
612 }
613
614 @article{ hanthor:randsort,
615   title={{Integer Sorting in $\O(n\sqrt{\log\log n})$ Expected Time and Linear Space}},
616   author={Han, Y. and Thorup, M.},
617   journal={Proceedings of the 43rd Symposium on Foundations of Computer Science},
618   pages={135--144},
619   year={2002},
620   publisher={IEEE Computer Society Washington, DC, USA}
621 }
622
623 @article{ ito:newrap,
624   title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}},
625   author={Ito, M. and Takagi, N. and Yajima, S.},
626   journal={Proc. 12th IEEE Symp. Computer Arithmetic},
627   pages={2--9},
628   year={1995}
629 }
630
631 @article{ brodnik:lsb,
632   title={{Computation of the least significant set bit}},
633   author={Brodnik, A.},
634   journal={Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, Slovenia},
635   year={1993}
636 }
637
638 @article{ turan:succinct,
639   title={{Succinct representation of graphs.}},
640   author={Tur\'an, G.},
641   journal={Discrete Applied Mathematics},
642   volume={8},
643   number={3},
644   pages={289--294},
645   year={1984}
646 }
647
648 @book{ jones:haskell,
649   title={{Haskell 98 Language and Libraries: The Revised Report}},
650   author={Jones, P. and Simon, L.},
651   year={2003},
652   publisher={Cambridge University Press}
653 }
654
655 @article{ mader:dens,
656   title={{Homomorphieeigenschaften und mittlere Kantendichte von Graphen}},
657   author={Mader, W.},
658   journal={Mathematische Annalen},
659   volume={174},
660   number={4},
661   pages={265--268},
662   year={1967},
663   publisher={Springer},
664   note={German}
665 }
666
667 @inproceedings{ gustedt:parallel,
668     author = "Jens Gustedt",
669     title = "Minimum Spanning Trees for Minor-Closed Graph Classes in Parallel",
670     booktitle = "Symposium on Theoretical Aspects of Computer Science",
671     pages = "421-431",
672     year = "1998",
673     url = "citeseer.ist.psu.edu/223918.html"
674 }
675
676 @article{ myrvold:rank,
677   title={{Ranking and unranking permutations in linear time}},
678   author={Myrvold, W.J. and Ruskey, F.},
679   journal={Information Processing Letters},
680   volume={79},
681   number={6},
682   pages={281--284},
683   year={2001}
684 }
685
686 @inproceedings{ critani:rau,
687   title={{Ranking and unranking permutations with applications}},
688   author={Critani, F. and Dall'Aglio, M. and Di Biase, G.},
689   booktitle={Innovation in Mathematics: Proceedings of Second International Mathematica Symposium},
690   pages = "99-106",
691   year = "1997"
692 }
693
694 @article{ ruskey:ham,
695   title={{The Hamiltonicity of directed-Cayley graphs (or: A tale of backtracking)}},
696   author={Ruskey, F. and Jiang, M. and Weston, A.},
697   journal={Discrete Appl. Math},
698   volume={57},
699   pages={75--83},
700   year={1995}
701 }
702
703 @article{ ruskey:hce,
704   title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn}},
705   author={Ruskey, F. and Savage, C.D.},
706   journal={SIAM Journal on Discrete Mathematics},
707   volume={6},
708   number={1},
709   pages={152--166},
710   year={1993}
711 }
712
713 @article{ liehe:raulow,
714   title={{Ranking and Unranking of Lexicographically Ordered Words: An Average-Case Analysis}},
715   author={Liebehenschel, J.},
716   journal={Journal of Automata, Languages and Combinatorics},
717   volume={2},
718   number={4},
719   pages={227--268},
720   year={1997}
721 }
722
723 @book{ reingold:catp,
724   title={{Combinatorial Algorithms: Theory and Practice}},
725   author={Reingold, E.M.},
726   year={1977},
727   publisher={Prentice Hall College Div}
728 }
729
730 @inproceedings{ dietz:oal,
731  author = {Paul F. Dietz},
732  title = {Optimal Algorithms for List Indexing and Subset Rank},
733  booktitle = {WADS '89: Proceedings of the Workshop on Algorithms and Data Structures},
734  year = {1989},
735  isbn = {3-540-51542-9},
736  pages = {39--46},
737  publisher = {Springer-Verlag},
738  address = {London, UK},
739 }
740
741 @book { ss:fifteen,
742   title={{The 15 Puzzle Book}},
743   author={Slocum, J. and Sonneveld D.},
744   year={2006},
745   publisher={The Slocum Puzzle Foundation, Beverly Hills, CA, USA}
746 }
747
748 @article{ rs:wagner,
749   title={{Graph minors: XX. Wagner's Conjecture}},
750   author={Robertson, N. and Seymour, P. D.},
751   journal={Journal of Combinatorial Theory Series B},
752   volume={92},
753   number={2},
754   pages={325--357},
755   year={2004},
756   publisher={Academic Press, Inc. Orlando, FL, USA}
757 }
758
759 @book{ matnes:idm,
760   title={{Invitation to Discrete Mathematics}},
761   author={Matou{\v{s}}ek, J. and Ne{\v{s}}et{\v{r}}il, J.},
762   year={1998},
763   publisher={Oxford University Press}
764 }
765
766 @article{ stanley:econe,
767   title={{Enumerative combinatorics. Vol. 1}},
768   author={Stanley, R.P.},
769   journal={Cambridge Studies in Advanced Mathematics},
770   volume={49},
771   year={1997}
772 }
773
774 @article{ kaplansky:rooks,
775   title={{The problem of the rooks and its applications}},
776   author={Kaplansky, I. and Riordan, J.},
777   journal={Duke Math. J},
778   volume={13},
779   number={2},
780   pages={259--268},
781   year={1946}
782 }
783
784 @article{ dinic:flow,
785   author = {E. A. Dinic},
786   title = {Algorithm for solution of a problem of maximum flow in networks with power estimation},
787   journal = {Soviet Math. Dokl.},
788   volume = {11},
789   year = {1970},
790   pages = {1277--1280}
791 }
792
793 @article{ even:dinic,
794   author = {Shimon Even and Robert Endre Tarjan},
795   title = {Network Flow and Testing Graph Connectivity},
796   publisher = {SIAM},
797   year = {1975},
798   journal = {SIAM Journal on Computing},
799   volume = {4},
800   number = {4},
801   pages = {507--518},
802   url = {http://link.aip.org/link/?SMJ/4/507/1},
803   doi = {10.1137/0204043}
804 }
805
806 @article{ valiant:permanent,
807   title={{The complexity of computing the permanent}},
808   author={Valiant, L. G.},
809   journal={Theoretical Computer Science},
810   volume={8},
811   number={2},
812   pages={189--201},
813   year={1979}
814 }
815
816 @article{ jerrum:permanent,
817   title={{A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries}},
818   author={Jerrum, M. and Sinclair, A. and Vigoda, E.},
819   journal={Journal of the ACM},
820   volume={51},
821   number={4},
822   pages={671--697},
823   year={2004}
824 }
825
826 @article{ kasteleyn:crystals,
827   title={{Graph theory and crystal physics}},
828   author={Kasteleyn, P. W.},
829   journal={Graph Theory and Theoretical Physics},
830   publisher={Academic Press, London},
831   pages={43--110},
832   year={1967}
833 }
834
835 @article{ yuster:matching,
836   title={{Maximum matching in graphs with an excluded minor}},
837   author={Yuster, R. and Zwick, U.},
838   journal={Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms},
839   pages={108--117},
840   year={2007},
841   publisher={Society for Industrial and Applied Mathematics Philadelphia, PA, USA}
842 }
843
844 @article{ mucha:matching,
845   title={{Maximum Matchings in Planar Graphs via Gaussian Elimination}},
846   author={Mucha, M. and Sankowski, P.},
847   journal={Algorithmica},
848   volume={45},
849   number={1},
850   pages={3--20},
851   year={2006},
852   publisher={Springer}
853 }
854
855 @article {lovasz:minors,
856   title={{Graph Minor Theory}},
857   author={Lov\'asz, L.},
858   journal={Bulletin of the American Mathematical Society},
859   volume={43},
860   number={1},
861   pages={75--86},
862   year={2005}
863 }
864
865 @article{ andersson:fusion,
866   title={{Fusion trees can be implemented with AC0 instructions only}},
867   author={Andersson, A. and Miltersen, P.B. and Thorup, M.},
868   journal={Theoretical Computer Science},
869   volume={215},
870   number={1-2},
871   pages={337--344},
872   year={1999},
873   publisher={Elsevier}
874 }
875
876 @article{ thorup:rampq,
877   title={{On RAM priority queues}},
878   author={THORUP, M.},
879   journal={SIAM journal on computing(Print)},
880   volume={30},
881   number={1},
882   pages={86--109},
883   year={2001},
884   publisher={Society for Industrial and Applied Mathematics}
885 }
886
887 @article{ thorup:pqsssp,
888   title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}},
889   author={Thorup, M.},
890   journal={Proceedings of the thirty-fifth ACM Symposium on Theory of Computing},
891   pages={149--158},
892   year={2003},
893   publisher={ACM Press New York, NY, USA}
894 }
895
896 @article{ chazelle:mstapprox,
897   title={{Approximating the Minimum Spanning Tree Weight in Sublinear Time}},
898   author={Chazelle, B. and Rubinfeld, R. and Trevisan, L.},
899   journal={SIAM Journal on Computing},
900   volume={34},
901   pages={1370},
902   year={2005},
903   publisher={SIAM}
904 }
905
906 @inproceedings{ czumaj:metric,
907  author = {Artur Czumaj and Christian Sohler},
908  title = {Estimating the weight of metric minimum spanning trees in sublinear-time},
909  booktitle = {STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing},
910  year = {2004},
911  isbn = {1-58113-852-0},
912  pages = {175--183},
913  location = {Chicago, IL, USA},
914  doi = {http://doi.acm.org/10.1145/1007352.1007386},
915  publisher = {ACM},
916  address = {New York, NY, USA},
917 }
918
919 @inproceedings{ czumaj:euclidean,
920  author = {Artur Czumaj and Funda Erg\"{u}n and Lance Fortnow and Avner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler},
921  title = {Sublinear-time approximation of Euclidean minimum spanning tree},
922  booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms},
923  year = {2003},
924  isbn = {0-89871-538-5},
925  pages = {813--822},
926  location = {Baltimore, Maryland},
927  publisher = {Society for Industrial and Applied Mathematics},
928  address = {Philadelphia, PA, USA},
929 }
930
931 @book{ ieee:binfp,
932   author = {IEEE},
933   title = {IEEE Standard 754-1985 for Binary Floating-point Arithmetic},
934   year = {1985},
935   publisher = {IEEE}
936 }
937
938 @article{ dgoldberg:fp,
939   title={{What every computer scientist should know about floating-point arithmetic}},
940   author={Goldberg, D.},
941   journal={ACM Computing Surveys (CSUR)},
942   volume={23},
943   number={1},
944   pages={5--48},
945   year={1991},
946   publisher={ACM Press New York, NY, USA}
947 }
948
949 @article{ thorup:floatint,
950   title={{Floats, Integers, and Single Source Shortest Paths}},
951   author={Thorup, M.},
952   journal={Journal of Algorithms},
953   volume={35},
954   number={2},
955   pages={189--201},
956   year={2000},
957   publisher={Academic Press}
958 }
959
960 @article{ shamos:closest,
961   title={{Closest-point problems}},
962   author={Shamos, M. I. and Hoey, D.},
963   journal={Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science},
964   pages={151--162},
965   year={1975}
966 }
967
968 @article{ fortune:voronoi,
969   title={{A sweepline algorithm for Voronoi diagrams}},
970   author={Fortune, S.},
971   journal={Algorithmica},
972   volume={2},
973   number={1},
974   pages={153--174},
975   year={1987},
976   publisher={Springer}
977 }
978
979 @article{ zhou:nodel,
980   title={{Efficient minimum spanning tree construction without Delaunay triangulation}},
981   author={Zhou, H. and Shenoy, N. and Nicholls, W.},
982   journal={Information Processing Letters},
983   volume={81},
984   number={5},
985   pages={271--276},
986   year={2002},
987   publisher={Elsevier}
988 }
989
990 @techreport{ eppstein:spanning,
991   title={{Spanning Trees and Spanners}},
992   author={Eppstein, D.},
993   year={1996},
994   institution={Information and Computer Science, University of California, Irvine}
995 }
996
997 @article{ garey:steiner,
998   title={{The Complexity of Computing Steiner Minimal Trees}},
999   author={Garey, M.R. and Graham, R.L. and Johnson, D.S.},
1000   journal={SIAM Journal on Applied Mathematics},
1001   volume={32},
1002   number={4},
1003   pages={835--859},
1004   year={1977},
1005 }
1006
1007 @article{ garey:rectisteiner,
1008   title={{The Rectilinear Steiner Tree Problem is NP-Complete}},
1009   author={Garey, M.R. and Johnson, D.S.},
1010   journal={SIAM Journal on Applied Mathematics},
1011   volume={32},
1012   number={4},
1013   pages={826--834},
1014   year={1977},
1015 }
1016
1017 @article{ proemel:steiner,
1018   title={{A new approximation algorithm for the Steiner tree problem with performance ratio $5/3$}},
1019   author={Promel, H.J. and Steger, A.},
1020   journal={Journal of Algorithms},
1021   volume={36},
1022   pages={89--101},
1023   year={2000}
1024 }
1025
1026 @article{ arora:tspapx,
1027   title={{Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems}},
1028   author={Arora, S.},
1029   journal={Journal of the ACM (JACM)},
1030   volume={45},
1031   number={5},
1032   pages={753--782},
1033   year={1998},
1034   publisher={ACM Press New York, NY, USA}
1035 }