From 6269bd20ae4de28ba017c8932fe61f89116901e3 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 14 Jan 2008 20:18:47 +0100 Subject: [PATCH] Added bibliography. --- Makefile | 7 +- biblio.bib | 266 +++++++++++++++++++++++++++++++++++++++++++++++++++++ cover.tex | 2 +- macros.tex | 20 +++- saga.tex | 4 + 5 files changed, 292 insertions(+), 7 deletions(-) create mode 100644 biblio.bib diff --git a/Makefile b/Makefile index 14143de..a098e21 100644 --- a/Makefile +++ b/Makefile @@ -2,11 +2,10 @@ all: saga.ps CHAPTERS=cover -saga.dvi: saga.tex $(addsuffix .tex,$(CHAPTERS)) macros.tex - csplain $< - %.dvi: %.tex macros.tex - csplain $< + tex $< && if grep -q citation $*.aux ; then bibtex $* && tex $< && tex $< ; fi + +saga.dvi: $(addsuffix .tex,$(CHAPTERS)) %.ps: %.dvi dvips -D600 -o $@ -t a4 $< diff --git a/biblio.bib b/biblio.bib new file mode 100644 index 0000000..e1ed226 --- /dev/null +++ b/biblio.bib @@ -0,0 +1,266 @@ +@inproceedings{ bender00lca, + author = "Michael A. Bender and Martin Farach-Colton", + title = "The {LCA} Problem Revisited", + booktitle = "Latin American Theoretical {INformatics}", + pages = "88-94", + year = "2000", + url = "citeseer.ist.psu.edu/bender00lca.html" } + +@inproceedings{ frederickson91ambivalent, + 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", + pages = "632-641", + year = "1991", + url = "citeseer.ist.psu.edu/frederickson91ambivalent.html" } + +@article{ tarjan84setunion, + author = {Robert E. Tarjan and Jan van Leeuwen}, + title = {Worst-case Analysis of Set Union Algorithms}, + journal = {J. ACM}, + volume = {31}, + number = {2}, + year = {1984}, + issn = {0004-5411}, + pages = {245--281}, + doi = {http://doi.acm.org/10.1145/62.2160}, + publisher = {ACM Press}, + address = {New York, NY, USA}, +} + +@inproceedings { fw90trans, + author = "M. Fredman and D. E. Willard", + title = "{Trans-dichotomous algorithms for minimum spanning trees and shortest paths}", + booktitle = "{Proceedings of FOCS'90}", + pages = "719--725", + year = "1990" +} + +@article{boas77, + author = {Peter van Emde Boas}, + title = {Preserving Order in a Forest in Less Than Logarithmic Time + and Linear Space.}, + journal = {Inf. Process. Lett.}, + volume = {6}, + number = {3}, + year = {1977}, + pages = {80-82}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} + +@inproceedings{thorup03ac0, + author = {Mikkel Thorup}, + title = {On AC0 implementations of fusion trees and atomic heaps}, + booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms}, + year = {2003}, + isbn = {0-89871-538-5}, + pages = {699--707}, + location = {Baltimore, Maryland}, + publisher = {Society for Industrial and Applied Mathematics}, + address = {Philadelphia, PA, USA}, + } + +@article{ benamram95what, + author = "Ben-Amram", + title = "What is a ``Pointer Machine''?", + journal = "SIGACTN: SIGACT News (ACM Special Interest Group on Automata and Computability Theory)", + volume = "26", + year = "1995", + url = "citeseer.ist.psu.edu/ben-amram95what.html" } + +@article{ matsui:planar, + author = "Tomomi Matsui", + title = "{The Minimum Spanning tree Problem on a Planar Graph}", + journal = "Discrete Applied Mathematics", + volume = "58", + year = "1995", + pages = "91--94", + url = "citeseer.nj.nec.com/2319.html" +} + +@article{ chazelle:ackermann, + author = "Bernard Chazelle", + title = "{A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity}", + journal = jacm, + volume = "47", + pages = "1028--1047", + year = "2000" +} + +@article{ nesetril:history, + author = "Jaroslav Ne{\v{s}}et{\v{r}}il", + title = "{Some remarks on the history of MST-problem}", + journal = "Archivum Mathematicum", + volume = "33", + pages = "15--22", + year = "1997" +} + +@article{ nesetril:boruvka, + author = "Jaroslav Ne{\v{s}}et{\v{r}}il and E. Milkov{\'a} and H. Ne{\v{s}}et{\v{r}}ilov{\'a}", + title = "{Otakar Bor{\accent23u}vka on Minimum Spanning Tree Problem}", + journal = "Discrete Mathematics", + volume = "233(1--3)", + pages = "3--36", + year = "2001" +} + +@unpublished { nesetril:minors, + author = "Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice Ossona de Mendez", + title = "{Colorings and Homomorphism of Minor Closed Classes}", + note = "To appear in {\it Pollack-Goodman Festschrift,} Springer Verlag, 2002." +} + +@article { boruvka:ojistem, + author = "Otakar Bor{\accent23u}vka", + title = "{O jist\'em probl\'emu minim\'aln\'\i{}m (About a Certain Minimal Problem)}", + journal = "Pr\'ace mor. p\v{r}\'\i{}rodov\v{e}d. spol. v~Brn\v{e}", + volume = "III", + year = "1926", + pages = "37--58", + note = "Czech with German summary" +} + +@book { tarjan:dsna, + author = "Robert E. Tarjan", + title = "{Data structures and network algorithms}", + series = "{CMBS-NSF Regional Conf. Series in Appl. Math.}", + volume = 44, + year = "1983", + publisher = "SIAM" +} + +@article { gh:history, + author = "R. L. Graham and P. Hell", + title = "{On the history of the minimum spanning tree problem}", + journal = "{Annals of the History of Computing}", + volume = "7", + year = "1985", + pages = "43--57" +} + +@techreport { pettie:ackermann, + author = "Seth Pettie", + title = "{Finding minimum spanning trees in $O(m\alpha(m,n))$ time}", + institution = "Univ. of Texas at Austin", + year = "1999", + number = "TR99-23", + type = "Tech Report" +} + +@inproceedings { pettie:optimal, + author = "Seth Pettie and Vijaya Ramachandran", + title = "{An Optimal Minimum Spanning Tree Algorithm}", + booktitle = "{Proceedings of ICALP'2000}", + year = "2000", + publisher = "Springer Verlag", + pages = "49--60" +} + +@article { karger:randomized, + author = "D. R. Karger and P. N. Klein and R. E. Tarjan", + title = "{Linear expected-time algorithms for connectivity problems}", + journal = jacm, + volume = "42", + pages = "321--328", + year = "1995" +} + +@article { frederickson:online, + author = "Greg N. Frederickson", + title = "{Data structures for on-line updating of minimum spanning trees}", + journal = "{SIAM Journal on Computing}", + volume = "14", + pages = "781--798", + year = "1985" +} + +@article { mm:mst, + author = "Martin Mare\v{s}", + title = "{Two linear time algorithms for MST on minor closed graph classes}", + journal = "{Archivum Mathematicum}", + volume = "40", + pages = "315--320", + year = "2004" +} + +@article{ ft:fibonacci, + author = {Michael L. Fredman and Robert Endre Tarjan}, + title = {Fibonacci heaps and their uses in improved network optimization algorithms}, + journal = {J. ACM}, + volume = {34}, + number = {3}, + year = {1987}, + issn = {0004-5411}, + pages = {596--615}, + doi = {http://doi.acm.org/10.1145/28869.28874}, + publisher = {ACM Press}, + address = {New York, NY, USA}, + } + +@article{ komlos:verify, + author = {J{\'a}nos Koml{\'o}s}, + title = {Linear verification for spanning trees.}, + journal = {Combinatorica}, + volume = {5}, + number = {1}, + year = {1985}, + pages = {57--65}, + bibsource = {DBLP, http://dblp.uni-trier.de} +} + +@inproceedings{ king:verify, + author = "Valerie King", + title = "A Simpler Minimum Spanning Tree Verification Algorithm", + booktitle = "Workshop on Algorithms and Data Structures", + pages = "440--448", + year = "1995", + url = "citeseer.ist.psu.edu/king95simpler.html" } + +@book { schrijver, + author = "Alexander Schrijver", + title = "{Combinatorial Optimization --- Polyhedra and Efficiency}", + series = "Algorithms and Combinatorics", + volume = 24, + year = 2003, + publisher = "Springer Verlag" +} + +@inproceedings{ thorup:ac0, + author = {Mikkel Thorup}, + title = {{On ${\rm AC}^0$ Implementations of Fusion Trees and Atomic Heaps}}, + booktitle = {SODA '03: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms}, + year = {2003}, + isbn = {0-89871-538-5}, + pages = {699--707}, + location = {Baltimore, Maryland}, + publisher = {Society for Industrial and Applied Mathematics}, + address = {Philadelphia, PA, USA}, +} + +@article{ kruskal:mst, + title={{On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem}}, + 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, + title={{Graph Theory}}, + author={Diestel, R.}, + year={2005}, + publisher={Springer-Verlag Berlin and Heidelberg GmbH \& Co. K} +} + +@article{ thorup:pq, + title={{Integer priority queues with decrease key in constant time and the single source shortest paths problem}}, + author={Thorup, M.}, + journal={Proceedings of the thirty-fifth ACM symposium on Theory of computing}, + pages={149--158}, + year={2003}, + publisher={ACM Press New York, NY, USA} +} diff --git a/cover.tex b/cover.tex index de2b9d7..cece437 100644 --- a/cover.tex +++ b/cover.tex @@ -21,7 +21,7 @@ rarity of metasulphur. \section{Introduction} We will demonstrate our approach on several examples of potions which are -usually considered very volatile and dangerous to prepare~[1]. +usually considered very volatile and dangerous to prepare~\cite{bender00lca}. There are two basic kinds of ingredients in our recipes (except for the metasulphur, which fits neither category, as expected): herbs and parts of bodies of living diff --git a/macros.tex b/macros.tex index 68bba1e..206c037 100644 --- a/macros.tex +++ b/macros.tex @@ -2,6 +2,7 @@ % (c) 2008 Martin Mares \input epsf.tex +\input btxmac.tex \catcode`@=11 @@ -30,7 +31,6 @@ \def\<#1>{\leavevmode\hbox{\it #1\/}} \let\>=\noindent \def\qed{{\parfillskip=0pt\allowbreak\hfill\nobreak $\spadesuit$\par}} -\let\endpart=\bye % Footnotes \newcount\footcnt @@ -96,7 +96,7 @@ \def\it{\fam\itfam\twelveit} \def\bo{\fam\bffam\twelveb} \def\bf{\fam\bffam\twelvebf} -\def\tt{\fam\ttfam\twelvett\hyphenchar\currentfont=-1\relax} +\def\tt{\fam\ttfam\twelvett\hyphenchar\twelvett=-1\relax} \def\sc{\twelvesc} \def\sl{\fam\slfam\twelvesl} @@ -323,6 +323,22 @@ \def\secref#1{\ref{sec#1}} \def\thmref#1{\ref{thm#1}} +%%% Bibliography %%% + +\bibliographystyle{abbrv} +\def\dumpbib{ + \def\bblhook{\parskip=2pt plus 1pt minus 0.5pt} + \bibliography{biblio} +} + +%%% Stand-alone chapters %%% + +\def\endpart{ + \section{Bibliography} + \dumpbib + \vfill\supereject\end +} + %%% The End %%% \catcode`@=12 diff --git a/saga.tex b/saga.tex index ecfbba2..46e5bc1 100644 --- a/saga.tex +++ b/saga.tex @@ -3,4 +3,8 @@ \input cover.tex +\chapter{Bibliography} + +\dumpbib + \bye -- 2.39.2