X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=biblio.bib;h=765bf723ce34b59f47b7c7315ee55a814b743992;hb=9a0ea083594219f5d391bf6f5cc59d867a815c9e;hp=73c04bb6e03ea03104d49fbc42ce1a1daecba8b3;hpb=4bb28a9fa18be89c1992fce6db8a5cb70fbba804;p=saga.git

diff --git a/biblio.bib b/biblio.bib
index 73c04bb..765bf72 100644
--- a/biblio.bib
+++ b/biblio.bib
@@ -46,7 +46,6 @@
   number={2},
   pages={215--225},
   year={1975},
-  publisher={ACM Press New York, NY, USA}
 }
 
 @inproceedings { fw:transdich,
@@ -108,6 +107,8 @@
     author = "Jaroslav Ne{\v{s}}et{\v{r}}il",
     title = "{Some remarks on the history of MST-problem}",
     journal = "Archivum Mathematicum",
+    publisher = "Masaryk University",
+    address = "Brno, Czech Republic",
     volume = "33",
     pages = "15--22",
     year = "1997"
@@ -168,13 +169,13 @@
     series = "{CMBS-NSF Regional Conference Series in Applied Mathematics}",
     volume = 44,
     year = "1983",
-    publisher = "SIAM"
+    publisher = "Society for Industrial and Applied Mathematics"
 }
 
 @techreport { pettie:ackermann,
     author = "Seth Pettie",
-    title = "{Finding minimum spanning trees in $\O(m\alpha(m,n))$ time}",
-    institution = "Univ. of Texas at Austin",
+    title = "{Finding minimum spanning trees in $\O(m\timesalpha(m,n))$ time}",
+    institution = "University of Texas at Austin",
     year = "1999",
     number = "TR99-23",
     type = "Tech Report"
@@ -246,6 +247,8 @@
    author = "Martin Mare\v{s}",
    title = "{Two linear time algorithms for MST on minor closed graph classes}",
    journal = "{Archivum Mathematicum}",
+   publisher = "Masaryk University",
+   address = "Brno, Czech Republic",
    volume = "40",
    pages = "315--320",
    year = "2004"
@@ -257,7 +260,7 @@
   booktitle = "Algorithms --- ESA 2007: 15th Annual European Symposium",
   location = "Eilat, Israel, October 8--10, 2007",
   volume = "4698",
-  series = "Lecture Notes in Computer Science",
+  series = {{Lecture Notes in Computer Science}},
   pages = "187--193",
   publisher = "Springer Verlag",
   year = "2007",
@@ -320,7 +323,7 @@
 @inproceedings{ thorup:aczero,
  author = {Mikkel Thorup},
  title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}},
- booktitle = {SODA '03: Proceedings of the 14th annual ACM-SIAM Symposium on Discrete algorithms},
+ booktitle = {SODA 2003: Proceedings of the 14th annual ACM-SIAM Symposium on Discrete algorithms},
  year = {2003},
  isbn = {0-89871-538-5},
  pages = {699--707},
@@ -329,13 +332,12 @@
 
 @article{ kruskal:mst,
   title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}},
-  author={Kruskal Jr, J. B.},
+  author={Kruskal, Jr, J. B.},
   journal={Proceedings of the American Mathematical Society},
   volume={7},
   number={1},
   pages={48--50},
   year={1956},
-  publisher={JSTOR}
 }
 
 @book{ diestel:gt,
@@ -460,7 +462,7 @@
   author = "S. Pettie",
   title = "An inverse-{A}ckermann style lower bound for the online minimum spanning
     tree verification problem",
-  booktitle = "FOCS 2002: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science",
+  booktitle = "FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science",
   year = "2002",
   url = "citeseer.ist.psu.edu/article/pettie02inverseackermann.html"
 }
@@ -479,7 +481,7 @@
 @inproceedings{ pettie:minirand,
  author = {Seth Pettie and Vijaya Ramachandran},
  title = {Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms},
- booktitle = {SODA '02: Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms},
+ booktitle = {SODA 2002: Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms},
  year = {2002},
  isbn = {0-89871-513-X},
  pages = {713--722},
@@ -502,15 +504,14 @@
   number={1},
   pages={57--74},
   year={1997},
-  publisher={Elsevier}
 }
 
 @inproceedings{ katriel:cycle,
   author = "I. Katriel and P. Sanders and J. Tr{\"a}ff",
   title = "A practical minimum spanning tree algorithm using the cycle property",
   booktitle = "Algorithms --- ESA 2003: 11th European Symposium",
-  number = "2832",
-  series = "LNCS",
+  volume = "2832",
+  series = "Lecture Notes in Computer Science",
   pages = "679--690",
   publisher = "Springer Verlag",
   year = "2003",
@@ -533,16 +534,15 @@
   number={2},
   pages={109--122},
   year={1986},
-  publisher={Springer Verlag}
 }
 
-@Unpublished{ eisner:tutorial,
+@online{ eisner:tutorial,
   author = 	 {Jason Eisner},
   title = 	 {{State-of-the-Art Algorithms for Minimum Spanning
                   Trees: A~Tutorial Discussion}},
   note = 	 {Manuscript available online (78 pages), University of Pennsylvania},
   year =	 1997,
-  url =		 {http://cs.jhu.edu/~jason/papers/#ms97},
+  url =		 {http://cs.jhu.edu/{\char126}jason/papers/\#ms97},
 }
 
 @article{ aho:lca,
@@ -560,7 +560,6 @@
  year = {1997},
  isbn = {0-201-89683-4},
  publisher = {Addison Wesley Longman Publishing Co., Inc.},
- address = {Redwood City, CA, USA},
 }
 
 @book{ knuth:seminalg,
@@ -569,7 +568,6 @@
  year = {1997},
  isbn = {978-0-201-89684-8},
  publisher = {Addison Wesley Longman Publishing Co., Inc.},
- address = {Redwood City, CA, USA},
 }
 
 @book{ knuth:sas,
@@ -578,7 +576,6 @@
   year = {1998},
   isbn = {978-0-201-89685-5},
   publisher = {Addison Wesley Longman Publishing Co., Inc.},
-  address = {Redwood City, CA, USA},
 }
 
 @inproceedings{ hagerup:wordram,
@@ -652,10 +649,10 @@
   year={1993},
 }
 
-@article{ han:detsort,
+@inproceedings{ han:detsort,
   title={{Deterministic sorting in $\O(n \log\log n)$ time and linear space}},
   author={Han, Y.},
-  journal={Proceedings of the 34th annual ACM Symposium on Theory of Computing},
+  booktitle={STOC 2002: Proceedings of the 34th annual ACM Symposium on Theory of Computing},
   pages={602--608},
   year={2002},
 }
@@ -663,15 +660,15 @@
 @inproceedings{ hanthor:randsort,
   title={{Integer Sorting in $\O(n\sqrt{\log\log n})$ Expected Time and Linear Space}},
   author={Han, Y. and Thorup, M.},
-  booktitle={Proceedings of the 43rd Symposium on Foundations of Computer Science},
+  booktitle={FOCS 2002: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science},
   pages={135--144},
   year={2002},
 }
 
-@article{ ito:newrap,
+@inproceedings{ ito:newrap,
   title={{Efficient Initial Approximation and Fast Converging Methods for Division and Square Root}},
   author={Ito, M. and Takagi, N. and Yajima, S.},
-  journal={Proc. 12th IEEE Symp. Computer Arithmetic},
+  booktitle={Proceedings of the 12th IEEE Symposium on Computer Arithmetic},
   pages={2--9},
   year={1995}
 }
@@ -749,7 +746,7 @@
 }
 
 @article{ ruskey:hce,
-  title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of Sn}},
+  title={{Hamilton Cycles that Extend Transposition Matchings in Cayley Graphs of $S_n$}},
   author={Ruskey, F. and Savage, C. D.},
   journal={SIAM Journal on Discrete Mathematics},
   volume={6},
@@ -772,7 +769,7 @@
   title={{Combinatorial Algorithms: Theory and Practice}},
   author={Reingold, E. M.},
   year={1977},
-  publisher={Prentice Hall College Div}
+  publisher={Prentice Hall College Div.}
 }
 
 @inproceedings{ dietz:oal,
@@ -808,12 +805,11 @@
   publisher={Oxford University Press}
 }
 
-@article{ stanley:econe,
-  title={{Enumerative combinatorics. Vol. 1}},
+@book{ stanley:econe,
+  title={{Enumerative Combinatorics. Vol. 1 (2nd ed.)}},
   author={Stanley, R. P.},
-  journal={Cambridge Studies in Advanced Mathematics},
-  volume={49},
-  year={1997}
+  publisher={Cambridge University Press},
+  year={2000}
 }
 
 @article{ kaplansky:rooks,
@@ -823,7 +819,8 @@
   volume={13},
   number={2},
   pages={259--268},
-  year={1946}
+  year={1946},
+  publisher={Duke University Press}
 }
 
 @article{ dinic:flow,
@@ -838,7 +835,6 @@
 @article{ even:dinic,
   author = {Shimon Even and Robert Endre Tarjan},
   title = {Network Flow and Testing Graph Connectivity},
-  publisher = {SIAM},
   year = {1975},
   journal = {SIAM Journal on Computing},
   volume = {4},
@@ -868,19 +864,20 @@
   year={2004}
 }
 
-@article{ kasteleyn:crystals,
+/* HACK: bibtex cannot handle a part of a book with its own name */
+@inproceedings{ kasteleyn:crystals,
   title={{Graph theory and crystal physics}},
   author={Kasteleyn, P. W.},
-  journal={Graph Theory and Theoretical Physics},
+  booktitle={Graph Theory and Theoretical Physics},
   publisher={Academic Press, London},
   pages={43--110},
   year={1967}
 }
 
-@article{ yuster:matching,
+@inproceedings{ yuster:matching,
   title={{Maximum matching in graphs with an excluded minor}},
   author={Yuster, R. and Zwick, U.},
-  journal={SODA 2007: Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms},
+  booktitle={SODA 2007: Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms},
   pages={108--117},
   year={2007},
 }
@@ -913,7 +910,6 @@
   number={1-2},
   pages={337--344},
   year={1999},
-  publisher={Elsevier}
 }
 
 @article{ thorup:rampq,
@@ -946,7 +942,7 @@
 @inproceedings{ czumaj:metric,
  author = {Artur Czumaj and Christian Sohler},
  title = {Estimating the weight of metric minimum spanning trees in sublinear-time},
- booktitle = {STOC '04: Proceedings of the 36th annual ACM Symposium on Theory of Computing},
+ booktitle = {STOC 2004: Proceedings of the 36th annual ACM Symposium on Theory of Computing},
  year = {2004},
  isbn = {1-58113-852-0},
  pages = {175--183},
@@ -955,12 +951,11 @@
 
 @inproceedings{ czumaj:euclidean,
  author = {Artur Czumaj and Funda Erg\"{u}n and Lance Fortnow and Avner Magen and Ilan Newman and Ronitt Rubinfeld and Christian Sohler},
- title = {Sublinear-time approximation of Euclidean minimum spanning tree},
- booktitle = {SODA '03: Proceedings of the 14th annual ACM-SIAM Symposium on Discrete Algorithms},
+ title = {{Sublinear-time approximation of Euclidean minimum spanning tree}},
+ booktitle = {SODA 2003: Proceedings of the 14th annual ACM-SIAM Symposium on Discrete Algorithms},
  year = {2003},
  isbn = {0-89871-538-5},
  pages = {813--822},
- publisher = {Society for Industrial and Applied Mathematics},
 }
 
 @book{ ieee:binfp,
@@ -993,7 +988,7 @@
 @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},
+  journal={FOCS '75: Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science},
   pages={151--162},
   year={1975}
 }
@@ -1087,8 +1082,8 @@
 
 @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 39th annual ACM Symposium on Theory of Computing},
+ title = {{An $\widetilde\O(mn)$ Gomory-Hu tree construction algorithm for unweighted graphs}},
+ booktitle = {STOC 2007: Proceedings of the 39th annual ACM Symposium on Theory of Computing},
  year = {2007},
  isbn = {978-1-59593-631-8},
  pages = {605--614},
@@ -1240,7 +1235,7 @@
   number={1},
   pages={118--133},
   year={1928},
-  publisher={Springer},
+  publisher={Springer Verlag},
   notes={In German}
 }
 
@@ -1250,7 +1245,6 @@
   journal={INTEGERS: The Electronic Journal of Combinatorial Number Theory},
   volume={2},
   number={A11},
-  pages={2},
   year={2002}
 }
 
@@ -1304,20 +1298,20 @@
   year={1997},
 }
 
-@article{ henzinger:mst,
+@inproceedings{ henzinger:mst,
   title={{Maintaining minimum spanning trees in dynamic graphs}},
   author={Henzinger, M. R. and King, V.},
-  journal={ICALP '97: Proceedings of the 24th International Colloquium on Automata, Languages and Programming},
+  booktitle={ICALP '97: Proceedings of the 24th International Colloquium on Automata, Languages and Programming},
   pages={594--604},
   year={1997},
 }
 
 @mastersthesis { mares:dga,
-  title={{Dynamick\'e grafov\'e algoritmy}},
+  title={{Dynamick\'e grafov\'e algoritmy (Dynamic Graph Algorithms)}},
   author={Martin Mare\v{s}},
   school={Charles University in Prague, Faculty of Math and Physics},
   year={2000},
-  notes={In Czech}
+  note={In Czech}
 }
 
 @techreport{ henzinger:twoec,
@@ -1363,7 +1357,7 @@
 @inproceedings{ thorup:nearopt,
  author = {Mikkel Thorup},
  title = {Near-optimal fully-dynamic graph connectivity},
- booktitle = {STOC '00: Proceedings of the 32nd annual ACM Symposium on Theory of Computing},
+ booktitle = {STOC 2000: Proceedings of the 32nd annual ACM Symposium on Theory of Computing},
  year = {2000},
  isbn = {1-58113-184-4},
  pages = {343--350},
@@ -1406,7 +1400,7 @@
 @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},
+  booktitle = {ICALP 2000: Proceedings of the 27th International Colloquium on Automata, Languages and Programming},
   year = {2000},
   isbn = {3-540-67715-1},
   pages = {61--72},
@@ -1468,27 +1462,24 @@
   year={1986},
 }
 
-@article{ pettie:pairing,
+@inproceedings{ pettie:pairing,
   author = {Seth Pettie},
   title = {Towards a Final Analysis of Pairing Heaps},
   booktitle = {FOCS 2005: Proceedings of the 46rd Annual IEEE Symposium on Foundations of Computer Science},
-  volume = {00},
   year = {2005},
-  isbn = {0-7695-2468-0},
   pages = {174-183},
-  doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.75},
 }
 
 @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}
+  publisher={Addison Wesley Longman Publishing Co., Inc.}
 }
 
 @techreport { mm:ga,
   author = "Martin Mare\v{s}",
-  title = "{Krajinou grafov\'ych algoritm\accent23u}",
+  title = "{Krajinou grafov\'ych algoritm\accent23u (Through the Landscape of Graph Algorithms)}",
   institution = "Institut Teoretick\'e Informatiky",
   address = "Praha, Czech Republic",
   year = "2007",
@@ -1499,7 +1490,7 @@
 
 @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},
+  title = {54.~ro\v{c}n\'\i{}k matematick\'e olympi\'ady na st\v{r}edn\'\i{}ch \v{s}kol\'ach (The 54th Year of the Math Olympiad at High Schools)},
   publisher = {Jednota \v{c}esk\'ych matematik\accent23u a fyzik\accent23u},
   address = {Praha},
   year = {2007},
@@ -1520,7 +1511,7 @@
 }
 
 @article{ kostochka:lbh,
-  title={{Lower bound of the hadwiger number of graphs by their average degree}},
+  title={{Lower bound of the Hadwiger number of graphs by their average degree}},
   author={Kostochka, A. V.},
   journal={Combinatorica},
   volume={4},