From 88814cec381a24a468e3c483f27b228e7e62d548 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 13 Sep 2008 15:55:56 +0200 Subject: [PATCH] More fixes to bugs reported by Patrice. --- TODO | 5 ----- adv.tex | 6 +++--- biblio.bib | 10 ++++++++++ mst.tex | 2 +- pref.tex | 2 +- 5 files changed, 15 insertions(+), 10 deletions(-) diff --git a/TODO b/TODO index cb7c13b..b3291ca 100644 --- a/TODO +++ b/TODO @@ -25,11 +25,6 @@ Diaz: Patrice: > Remark on 2.5.1: polynomial time could be replaced by sub-exponential time. -- For 1.5.6, you should probably quote D. Cheriton and R.E. Tarjan. - Finding Minimum Spanning Trees. SIAM J. on Comp. 5(4) (1976) pp. - 724-742. who gave a linear time algorithm for planar graphs, extended by - Tarjan in 1983 to proper minor closed classes (both quoted by Gustedt). - [XXX: The paper should be in the library at MS.] > In 3.1.12 and 3.1.16, you should make explicit the dependence of the running time with respect, for instance, to the Hadwiger number of the graph or to the maximal density nabla(G) of a minor of the graph, as diff --git a/adv.tex b/adv.tex index 35d5d9b..2a81be3 100644 --- a/adv.tex +++ b/adv.tex @@ -125,7 +125,7 @@ $G$~would contain a~subdivision of~$K_x$ and hence $K_x$ as a~minor. Let us return to the analysis of our algorithm. -\thmn{MST on minor-closed classes, Mare\v{s} \cite{mm:mst}}\id{mstmcc}% +\thmn{MST on minor-closed classes, Tarjan \cite{tarjan:dsna}}\id{mstmcc}% For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's algorithm (\ref{contbor}) finds the MST of any graph of this class in time $\O(n)$. (The constant hidden in the~$\O$ depends on the class.) @@ -256,8 +256,8 @@ has degree~9. \figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}} \rem -The observation in~Theorem~\ref{mstmcc} was also independently made by Gustedt \cite{gustedt:parallel}, -who studied a~parallel version of the Contractive Bor\o{u}vka's algorithm applied +The observation in~Theorem~\ref{mstmcc} was also used by Gustedt \cite{gustedt:parallel}, +to construct parallel version of the Contractive Bor\o{u}vka's algorithm applied to minor-closed classes. \rem diff --git a/biblio.bib b/biblio.bib index ad43a45..a21c1c0 100644 --- a/biblio.bib +++ b/biblio.bib @@ -1588,3 +1588,13 @@ volume={1675}, series={{Lecture Notes in Math}}, } + +@article{ cheriton:mst, + title={{Finding Minimum Spanning Trees}}, + author={Cheriton, D. and Tarjan, R.E.}, + journal={SIAM Journal on Computing}, + volume={5}, + number={4}, + pages={724--742}, + year={1976}, +} diff --git a/mst.tex b/mst.tex index 8a6a12a..d4bf952 100644 --- a/mst.tex +++ b/mst.tex @@ -654,7 +654,7 @@ in all iterations is $\O(\sum_i n_i^2) = \O(\sum_i n^2/4^i) = \O(n^2)$. On planar graphs, the algorithm runs much faster: -\thmn{Contractive Bor\o{u}vka on planar graphs}\id{planarbor}% +\thmn{Contractive Bor\o{u}vka's algorithm on planar graphs, Cheriton and Tarjan \cite{cheriton:mst}}\id{planarbor}% When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in time $\O(n)$. diff --git a/pref.tex b/pref.tex index cdff6b4..c06716c 100644 --- a/pref.tex +++ b/pref.tex @@ -37,7 +37,7 @@ included in the textbook \cite{mm:ga} which I have written for this course. \itemize\ibull \:The lower bound in Section \ref{contalg}. Not published yet. \:The tree isomorphism algorithm in Section \ref{bucketsort}. Not published yet. -\:Both algorithms for minor-closed graph classes in Section \ref{minorclosed}. Published in \cite{mm:mst}. +\:One of the algorithms for minor-closed graph classes in Section \ref{minorclosed}. Published in \cite{mm:mst}. \:The linear-time verification algorithm in Section \ref{verifysect} is a~simplification of the algorithm of King \cite{king:verifytwo} and it corrects many omissions in the original paper. Not published yet. -- 2.39.2