\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS5800}{Algorithms}{Spring 2011}{27 February 2011}{9}

\begin{center}
\Large{\bf Problem Set 4 (due Wednesday, March 9)}
\end{center}

{\bf 1. (10 points) Rate-Optimal Spanning Tree} 

You are working at a telecommunications company that has access to a
communication network $G$ connecting a set $V$ of nodes with a set $E$
of undirected edges (links).  Each link $e$ in $E$ has an associated
bandwidth $b_e$.  For any path $P$ in $G$ that connects two nodes, say
$u$ and $v$, we define the {\em rate}\/ $b(P)$ of $P$ to be the
minimum, over all edges $e$ in $P$, of $b_e$.  For any pair $u$ and
$v$ of vertices in $G$, the {\em best rate achievable between $u$ and
  $v$ in $G$}\/ is the maximum of $b(P)$ over all paths $P$ from $u$
to $v$ in $G$.

The era of cost-cutting has hit your firm as well.  One idea proposed
for trimming costs is to not use the entire network $G$, but instead
use a {\em spanning tree}\/ $T$ of $G$.

\begin{itemize}
\item[{\bf (a)}] Show that there exists a spanning tree $T$ of $G$ that has the
  following (seemingly incredible) property: for {\em every pair}\/
  $u$ and $v$ of vertices in $G$, the best rate achievable between $u$
  and $v$ in $T$ is equal to the best rate achievable between $u$ and
  $v$ in $G$.

\item[{\bf (b)}] Give an efficient algorithm to compute a spanning
  tree that satisfies the property stated in (a).
\end{itemize}

{\bf 2. (20 points)} Problem 5.21.

{\bf 3. (10 points)} Problem 5.29.

\end{document}