From 1c4448f5e08312e7fd6611b24469788ab92a9817 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 13 Sep 2008 17:58:53 +0200 Subject: [PATCH] Moved the Gustedt remark to Applications. --- adv.tex | 5 ----- appl.tex | 5 +++++ 2 files changed, 5 insertions(+), 5 deletions(-) diff --git a/adv.tex b/adv.tex index 2a81be3..f0370bb 100644 --- a/adv.tex +++ b/adv.tex @@ -255,11 +255,6 @@ has degree~9. \figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}} -\rem -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 The bound on the average degree needed to enforce a~$K_k$ minor, which we get from Theorem \ref{maderthm}, is very coarse. Kostochka \cite{kostochka:lbh} and independently Thomason \cite{thomason:efc} diff --git a/appl.tex b/appl.tex index f9d59ab..0b1b302 100644 --- a/appl.tex +++ b/appl.tex @@ -197,4 +197,9 @@ with linear work can be obtained by utilizing randomness, as shown for example by Pettie and Ramachandran \cite{pettie:minirand}, but so far only at the expense of higher time complexity. +Some of the algorithms for special classes of graphs also have their counterparts +in the parallel world. Most notably the Contractive Bor\o{u}vka's algorithm +for minor-closed graph classes (Theorem \ref{mstmcc}) has been parallized +by Gustedt \cite{gustedt:parallel}. + \endpart -- 2.39.2