number={2},
pages={215--225},
year={1975},
- publisher={ACM Press New York, NY, USA}
}
@inproceedings { fw:transdich,
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"
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"
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"
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",
@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},
@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,
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"
}
@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},
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",
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,
year = {1997},
isbn = {0-201-89683-4},
publisher = {Addison Wesley Longman Publishing Co., Inc.},
- address = {Redwood City, CA, USA},
}
@book{ knuth:seminalg,
year = {1997},
isbn = {978-0-201-89684-8},
publisher = {Addison Wesley Longman Publishing Co., Inc.},
- address = {Redwood City, CA, USA},
}
@book{ knuth:sas,
year = {1998},
isbn = {978-0-201-89685-5},
publisher = {Addison Wesley Longman Publishing Co., Inc.},
- address = {Redwood City, CA, USA},
}
@inproceedings{ hagerup:wordram,
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},
}
@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}
}
}
@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},
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,
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,
volume={13},
number={2},
pages={259--268},
- year={1946}
+ year={1946},
+ publisher={Duke University Press}
}
@article{ dinic:flow,
@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},
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},
}
number={1-2},
pages={337--344},
year={1999},
- publisher={Elsevier}
}
@article{ thorup:rampq,
@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},
@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,
@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}
}
@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},
number={1},
pages={118--133},
year={1928},
- publisher={Springer},
+ publisher={Springer Verlag},
notes={In German}
}
journal={INTEGERS: The Electronic Journal of Combinatorial Number Theory},
volume={2},
number={A11},
- pages={2},
year={2002}
}
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,
@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},
@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},
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",
@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},
}
@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},