\documentclass[12pt]{report}

\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{times}
\usepackage{amsmath, amsfonts}
\usepackage{setspace}

\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{notation}{Notation}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{proof}{Proof}

% <http://psl.cs.columbia.edu/phdczar/proposal.html>:
%
% The standard departmental thesis proposal format is the following:
%        30 pages
%        12 point type
%        1 inch margins all around = 6.5   inch column
%        (Total:  30 * 6.5   = 195 page-inches)
%
% For letter-size paper: 8.5 in x 11 in
% Latex Origin is 1''/1'', so measurements are relative to this.

\topmargin      0.0in
\headheight     0.0in
\headsep        0.0in
\oddsidemargin  0.5in
\evensidemargin 0.0in
\textheight     9.0in
\textwidth      6.0in
\setstretch{1.5}

\title{An Introduction to Interconnection Networks and Xmulator}
\begin{document}
\pagestyle{plain}
\pagenumbering{roman}



\begin{abstract}

$Broadcasting$  is an information dissemination problem in a
connected network, in which one node, called the $originator$,
disseminates a message to all other nodes by placing a series of
calls along the communication lines of the network. Once informed,
the nodes aid the originator in distributing the message. Finding
the broadcast time of a vertex in an arbitrary graph is
NP-complete. The problem is solved polynomially only for trees. In
\cite{SCH81} it is proved that the complexity of the problem of
determining the broadcast time of any vertex in an arbitrary tree
$T = (V, E)$ is $\Theta(|V|)$. In this proposal we continue
the search for polynomial algorithms for different classes of graphs.
We present an algorithm that determines the broadcast time of any originator in
an arbitrary unicyclic graph $G = (V, E)$ in $O(|V|)$ time. This,
combined with the obvious lower bound, gives a $\Theta(|V|)$
solution for the problem of determining the broadcast time of an
arbitrary originator in an arbitrary unicyclic graph. As a
byproduct, we also find a broadcast center of the unicyclic graph
(a vertex in $G$ with the minimum broadcast time). Using this
algorithm we give a $O(|V|)$ algorithm to find the broadcast time
(maximum broadcast time) of an arbitrary unicyclic graph. We then
suggest different classes of graphs where we believe broadcasting
can either be solved in polynomial time (such as cactus graphs and almost trees)
or good approximation algorithms can be obtained (k trees). 
We also try to solve the problem of constructing optimal unicyclic graphs
which are the garphs with maximum possible number of vertices for a 
given broadcast time. 
\end{abstract}

\pagebreak
\tableofcontents
\pagebreak

\cleardoublepage
\pagenumbering{arabic}
\chapter{\bf Introduction}
\label{sec:intro}

Even though modern day CPUs are getting faster every day, they
are still unable to solve a plethora of problems that scientists face.
One of the shortcomings of single CPU systems is the long amount of time needed
to solve the problem serially. A second shortcoming is that sometimes problems would
not even fit in the memory of a single CPU system.
The answer to these shortcummings is parallelism. Multiple CPUs
working on the same problem often can solve the problems more quickly.
Parallel computing is the term used to describe the usage of mutiple
CPUs to solve a single problem. Parallel computing, once only used
by scientist and engineers in expensive computer labs , is becoming
the default processing environment used by common people. The current
generation of processors are all multicore having several processing
units on the same board. These systems, however, share the same memory
and hence might face the second problem mentioned above: inability to fit
the problem in the memory.

There are different models for parallel computing.
One of the most common models is the MIMD (Multiple Instruction and Multiple
Data) which is sometimes referred to multicomputers or multiprocessors.
The different processors, working in parallel, will most probably need to exchange data among
each other. This is done either through a shared memory or an interconnection
network. Shared memory multicomputers have a limitation on the number of processors
that can be connected together. Hence, it is not practical if a very large number of
processors is to be connected. A more realistic way of designing multicomputers is to
make each processor have its own main memory. Communication between the
processors will be accomplished by passing messages using an interconnection network.
It turns out that the performance of these multicomputers not only depends on the
processing power of the processors but also on the performance of the
interconnection network in disseminating data among the processor. Research has shown that
the structural properties of a network determine many of its properties such as the
minimum broadcast time, ease of routing, and fault tolerance.

One of the fundamental information dissemination problems is broadcasting.
Broadcasting is a process in which a single message is sent from
one member of a network to all other members. Inefficient
broadcasting could degrade the performance of a network seriously.
Therefore, it is of a major interest to improve the performance of
a network by using efficient broadcasting algorithms.

$Broadcasting$ is an information dissemination problem in a
connected network, in which one node, called the $originator$,
must distribute a message to all other nodes by placing a series
of calls along the communication lines of the network. Once
informed, the informed nodes aid the originator in distributing
the message. This is assumed to take place in discrete time units.
The broadcasting is to be completed as quickly as possible,
subject to the following constrains:
\begin{itemize}
\item Each call involves only one informed node and one of its
uninformed neighbors. \item Each call requires one unit of time.
\item A node can participate in only one call per unit of time.
\item In one unit of time, many calls can be performed in
parallel.
\end{itemize}

A $broadcast$ $scheme$ of an originator $u$ is a set of calls that
completes the broadcasting in the network originated at vertex
$u$.

Formally, any network can be modelled as a connected graph $G =
(V,E)$, where $V$ is the set of vertices (or nodes) and $E$ is the
set of edges (or communication lines) between the vertices in
graph $G$.

Given a connected graph $G=(V,E)$ and a message originator, vertex
$u$, the $broadcast$ $time$ of vertex $u$, $b(u,G)$ or $b(u)$, is
the minimum number of time units required to complete broadcasting
from the vertex $u$. Note that for any vertex $u$ in a connected
graph $G$ on $n$ vertices, $b(u) \geq \lceil \log n \rceil$ since
during each time unit the number of informed vertices can at most
be doubled. The broadcast time $b(G)$ of the graph $G$ is defined
as $max\{b(u) |u \in V\}$. For surveys of results on broadcasting
and related problems, see Hedetniemi, Hedetniemi, and Liestman
\cite{HHL88}, Fraigniaud and Lazard \cite{PF94}, and Hromkovic,
Klasing, Monien, and Peine \cite{HKMP96}.

Determination of $b(u,G)$ or $b(u)$ for a vertex $u$ in an arbitrary
graph $G$ is $NP$-complete \cite{Jo79}. The proof of
$NP$-completeness is presented in \cite{SCH81}. Therefore, many
papers have presented approximation algorithms to determine the
broadcast time of any vertex in $G$ (see \cite{Ba98}, \cite{RBJS},
\cite{El02}, \cite{EK03}, \cite{UF90}, \cite{FP97}, \cite{FPSV},
\cite{FP99}, \cite{KP95}, \cite{RR94}, \cite{GW84}).

The heuristics \cite{RBJS} \cite{HS05} and \cite{HS07} are the best existing heuristics for broadcasting
in practice. Their performance is almost the same for commonly
used interconnection networks. However, the broadcast algorithm
from \cite{HS05} outperforms the broadcast algorithm from
\cite{RBJS} in three graph models from a network simulator ns-2
(see \cite{AC01, Ba98, MD96, ZC96}). Also, its time complexity is
$O(|E|)$, while the complexity of the algorithm from \cite{RBJS}
is $O(|V|^{2}\cdot |E|)$.

Since the problem is $NP$-complete in general, another direction
for research is to design polynomial algorithms that determine
the broadcast time of any vertex for a class of graphs. The broadcast
problem remains $NP$ complete even in some restricted classes of graphs namely,
planar graphs and bounded degree graphs \cite{JRS98}. The same paper also states
that graphs with certain decomposition properties have a polynomial solution.
One of the first class of graphs to be studied and found to have a linear solution
is the trees \cite{SCH81}.  The authors propose an algorithm that finds the broadcast
time of a given vertex in any arbitrary tree. They also find a broadcast
scheme of a given tree $T = (V, E)$ in linear time $O(|V|)$.

This proposal is organized as follows. In the next chapter we will present a
literature review of some of the important results in the broadcast problem.
In the third chapter we will present our results on unicyclic graphs which are
connected graphs with n edges and on n vertices. In chapter 4, we
outline different problems that we are planning to tackle in the coming 2 years.
The last chapter presents the conclusion of this proposal and presents a
time plan for our research.

\chapter{Literature Review}
\label{ch:LitRev}
In this chapter we review the major results of the broadcast
problem. In this work we will consider the classical model of
broadcasting known as telephone model. In this model a node in the
network can communicate with only one of its neighbors and both
vertices can exchange all the information they have. This model can
be compared to the telegraph model where not only a vertex can
communicate with one vertex at a time but only one of the vertices
sends information and the other one listens. The literature is full
of different models which will not be covered in this chapter. The
problem of finding the broadcast time of an arbitrary vertex in an
arbitrary graph was proved to be NP complete. The proof was done by
reducing the broadcast problem into the well known 3-dimensional
matching (3DM) problem which is known to be NP complete
\cite{SCH81}. 
The problem stays $NP$-complete even in more restricted classes of
graphs such as planar graphs \cite{JRS98} and bounded degree graphs \cite{MD94} and \cite{MM93}.

One can easily find an upper and a lower bound for the
broadcast time in general graphs. A lower bound on broadcast time
can be obtained by realizing that the number of informed vertices
can at most double in every round. Hence, $\lceil log n \rceil$ is a
lower bound. On the other hand in a connected graph there should be
at least one new informed vertex at every new round which implies
that an upper bound on the broadcast time is $n-1$.

Since finding an optimal broadcast scheme for general graphs was proved
to be computationally very expensive, research in this area focused
on four main problems:
\begin {enumerate}
\item Finding the broadcast time and scheme for special
classes of graphs.
\item Finding approximation algorithms and broadcast heuristics for
general graphs.
\item Constructing graphs whose broadcast time is $\lceil log n
\rceil$. These graphs are called broadcast graphs, $bg$. This is not
necessarily a difficult thing to do if one does not have any cost
concerns. For example a complete graph has broadcast time of $\lceil
log n \rceil$ but has way more edges than necessary. The research in
this area is directed towards constructing graphs on $n$ vertices
with broadcast time of $\lceil log n \rceil$ and minimum number of
edges, these graphs are called minimum broadcast graphs, $mbg$. The
number of edges of a $mbg$ on $n$ vertices is denoted by $B(n)$.
This function has proved to be difficult to compute and currently
its value is known only for a very small range of $n$, namely for
some values between 0 and 63, 4096, $2^k$ and $2^{k} -2$.
\item Another area if research has been in designing networks with
the least broadcast time possible given the number of vertices and
edges. Formally speaking, the $(n,m)$ problem is to design a graph
$G = (V,E)$ such that $|V| = n$, $|E| = m$ and $b(G) = b_{min}$ such
that there is no other graph $G'$ on $n$ vertices and $m$ edges such
that $b(G') < b(G)$.
\end {enumerate}

\section{Broadcast Time of Different Topologies}
In this section we will present some of the well known graph
topologies and their broadcast times. We will start with the path
topology, arguably the simplest graph topology, and gradually
consider more and more complex structures.
\subsection{The Path $P_n$}
A path $P_n$ on $n$ vertices numbered $v_1$ to $v_n$ has $n-1$ edges
and every vertex $v_i$, $2 \leq i \leq n -1$, has two edges
connecting it to vertices $v_{i-1}$ and $v_{i+1}$. The broadcast
time of $P_n$ is $n-1$ and this happens when the originator is one
of the end vertices, i.e. $v_1$ or $v_n$.

\subsection{The Cycle $C_n$}
The cycle $C_n$ (aka ring) on $n$ vertices is a path $P_n$ where the
end vertices $v_1$ and $v_n$ are also connected by an edge. $b(C_n)
= \lceil \frac{n}{2} \rceil$

\subsection{The tree $T_n$}
The tree $T_n$ on $n$ vertices is a connected graph with $n$ vertices and
$n-1$ edges. There is exactly one unique path between every two
vertices of a tree. The broadcast problem in general trees has been
solved in \cite{SCH81} where a linear algorithm was presented which
can find the optimal broadcast scheme of any vertex in an arbitrary
tree.

\subsection{The complete graph $K_n$}
The complete graph $K_n$ on $n$ vertices is a graph where every
vertex has an edge to each of the remaining $n-1$ edges. Hence, the
number of edges that a $K_n$ has is $n(n-1)$. It can be easily seen
that the $b(K_n) = \lceil log n \rceil$ because at every round,
except the last one, the number of informed vertices can double.

\subsection{The Hypercube $H_n$}
The hypercube of dimension $n$ is defined to be a graph on $2^n$
vertices numbered $v_0$ to $v_{2^n-1}$. Two vertices $v_i$ and $v_j$are neighbours if
the binary representations of $i$ and $j$ differ in exactly one position. For
example the vertices $v_2$ and $v_6$ in $H_3$ are neighbours because the binary representations 
010 and 110 differ only in the third position. The hypercube is one of the few infinite family
of graphs where the broadcast time is equal to $log n$, i.e. $b(H_n)=n$.

\subsection{The cube-connected cycles $CCC_m$}
The cube-connected cycles  on $m$ dimensions, $CCC_m$, is a graph $G=(V_m,E)$ where
$V_m = \{0,1, \cdots, m-1\} \times \{0,1\}^m$ and  $\{0,1\}^m$ denotes the set of binary strings
of length $m$. The set of edges, $E$, is defined as follows:
a vertex $v = (i, \alpha)$ has an edge with vertex $u =(j, \beta)$ iff one of the
following three conditions is satisfied:
\begin{enumerate}
\item $i = j$ and $\alpha$ differs from $\beta$ only in the $i^{th}$ bit.
\item $i = j - 1 \mod m$ and $\alpha = \beta$.
\item $i = j + 1 \mod m$ and $\alpha = \beta$.
\end{enumerate}
From \cite{LP88} we know that $b(CCC_m) = \lceil \frac{5m}{2} \rceil -1$.

\subsection{The butterfly network $BF_m$}
The butterfly network  on $m$ dimensions, $BF_m$, is a graph $G=(V_m,E)$ where
$V_m = \{0,1, \cdots, m-1\} \times \{0,1\}^m$ and  $\{0,1\}^m$ denotes the set of binary strings
of length $m$. The set of edges, $E$, is defined as follows:
a vertex $v = (i, \alpha)$ has an edge with vertex $u =(j, \beta)$ iff one of the
following three conditions is satisfied:
\begin{enumerate}
\item $i = j - 1 \mod m$ and $\alpha = \beta$.
\item $i = j + 1 \mod m$ and $\alpha = \beta$.
\item $i = j + 1 \mod m$ and $\alpha$ and $\beta$ differ only in the $((j-1)\mod m)^{th}$ bit.
\item $i = j - 1 \mod m$ and $\alpha$ and $\beta$ differ only in the $i^{th}$ bit.
\end{enumerate}
From \cite{KMPS94} we know that $1.7417m \leq b(BF_m) \leq 2m-1$.

\subsection{The shuffle-exchange network $SE_m$}
The $SE_m$ is a graph on $2^m$ vertices where the vertices are represented
by binary strings of length $m$. Two vertices $v$ and $u$ are 
connected iff one of the following holds:
\begin{enumerate}
\item $v$ and $u$ differ only in the last bit.
\item $u$ is obtained from $v$ by a single left cyclic shift.
\item $u$ is obtained from $v$ by a single right cyclic shift.
\end{enumerate}
From \cite{HJM93} we know that $b(SE_m) \leq 2m -1$.

\subsection{The de Bruijn Network $DB_m$}
The $DB_m$ on $m$ dimensions is a graph on $2^m$ verices which are
denoted by binary strings of length $m$. A vertex $v=a\alpha=\alpha'a'$, 
where $a,a' \in \{0,1\}$ and $\alpha$ and $\alpha'$ are binary strings
of length $m-1$, is connected to vertices $\alpha b$ where $b \in \{0,1\}$ 
and $b'\alpha'$ where $b' \in {0,1}$.
From \cite{KMPS94} we know that $b(SE_m) \geq 1.3171 m$ and from
\cite{BP88} we know that $b(SE_m) \leq 1.5m + 1.5$.

\subsection{The 2d Grid Network $G_{m,n}$}
The 2 dimensional grid network $G_{m,n}$ is a network on $mn$ vertices, 
having the topology of a mesh. A vertex $v$ labeled by a the tuple $(i,j)$ 
is connected to a maximum of 4 vertices, namely $(i-1,j)$, $(i,j-1)$, $(i+1,j)$, 
and $(i+1,j+1)$ for $1 < i < m$ and $1 < j < n$. The corner vertices have only 
2 neighbours, one on each dimension. The vertices on the sides have 3 neighbours,
for example $(0,j)$ is connected to $(0,j-1)$, $(0,j+1)$, $(1,j)$.
From \cite{HHL88} we know that $b(G_{m.n})= m+n-2$.


\section{Approximation Algorithms and Heuristics}
Since the general problem is $NP$ complete finding exact broadcast
algorithms is very inefficient for graphs of considerable size.
Therefore, people have resorted to either finding heuristics for finding
near optimal broadcast times or to approximation algorithms. Some
of the best broadcasting heuristics were presented in
\cite{RBJS} and \cite{HS05}. A matching based approach was utilized
to derive a broadcast algorithm of time complexity $O(Rn^2m log n)$,
where $R$ is the number of rounds needed to complete the broadcasting,
$n$ is the number of vertices and $m$ is the number of edges of the graph. The heuristic in
\cite{HS05}, TBA (tree based algorithm), reduces the complexity of
each round to $O(|E|)$. This algorithm performs as good as the one in
\cite{RBJS} in most of the commonly used interconnection networks and
produces better results in three graph generators. In \cite {HS07},
the TBAM (tree based algorithm with maximum matching) algorithm is introduced,
which modifies the TBA algorithm to produce even better results with a
little bit of price paid in the complexity of each round which is
$O(\sqrt{|V|}|E|)$ which is still much lower than that of \cite{RBJS}.

Even though the heuristic algorithms mentioned above produce good
results in practice, they cannot claim to have good results in
general. Approximation algorithms are those which have a theoretical
upper bound on the broadcast time in any graph. The first work of
this kind is \cite{KP95} where a $O(\sqrt{|V|})$ additive
approximation algorithm is presented. An algorithm A is considered
an $k-approximation$ scheme if the broadcast time calculated by A on
a graph $G$, $b(G,A) \leq k b(G)$. Similarly an approximation
algorithm is $k-additive$ if $b(G,A) \leq b(G) + k$. A randomized
algorithm was presented in \cite{RR94} which is an
$O(\frac{log^2|V|}{log log|V|})$. This algorithm is based on
calculating the poise of a graph. The poise of a tree T is defined
to be the maximum degree of T plus the the diameter of T. The poise
of a graph G, $P(G)$ is the minimum poise of all the spanning trees
of $G$. Calculating the poise of a graph is $NP$ complete. 
Ravi in \cite{RR94} presents a $O(log(n) P(G) + log^2n)$ algorithm
and shows that the broadcast time of a graph $G$ is related to the
poise of $G$ as follows: $b(G) = O(P(G) \frac{log n}{log logn})$.
The best theoretical upper bound is presented in \cite{EK03}. Their
approximation algorithm generates a broadcast algorithm with
broadcast time $O(\frac{log(|V|)}{loglog(|V|)})b(G)$. A multicast
approximation algorithm was given in \cite{Ba98} which is a $O(log k)$
where $k$ is the number of recipients in the graph $G$. This result can trivially
be generalized to broadcasting obtaining an $O(log|V|)$ approximation.

On the other hand, \cite{Schind00} studies the approximability of the broadcast time
and states that the broadcast time cannot be approximated within a
factor of $\frac{57}{56} - \epsilon.$

\section{Construction of Broadcast and Minimum Broadcast Graphs}
The previous section presented the problem of determining the
minimum time needed to complete broadcasting given a graph $G$. In
other words it is minimizing time. Another approach in the broadcast
problem is the one which optimizes the cost of the graph, namely the
number of edges needed by a graph under the constraint that
broadcasting should be completed in a certain amount of time. A
graph with a broadcast time of  $b(G) = \lceil log n \rceil$ is called a 
broadcast graph. A minimum broadcast graph , $mbg = (V,E)$, on n vertices , 
$|V| = n$, is defined to be a broadcast graph with the minimum possible number of 
vertices over all broadcast graphs on $n$ vertices. 
In the literature the number of edges of an $mbg$ on $n$ vertices 
is represented by $B(n)$. There has been considerable amount of research
in constructing minimum broadcast graphs on different number of vertices.
There is no known receipe of constructing graphs on $n$ vertices for any
integer value. After years of research the value of the function $B(n)$ is
known only for a very few values of $n$. Farley et al. \cite{} showed that 
hypercubes are mbg's which implies that $B(2^m) = m2^{m-1}$. Khachatrian
and Harutyunian \cite{Kh90} and Dineen et al. independently showed that
$B(2^m - 2)=(m-1)(2^{m-1}-1)$ for $m \geq 2$. Other than these relatively
large ranges, $B(n)$ has known values only for small $n$, namely $n \leq 63$,
$n=127$, $n=1023$, and $n=4095$. Direct construction of minimum broadcast 
graphs has proved to be a very difficult task. As a result, researchers have 
resorted to techniques that combines several broadcast graphs  with known
sizes to construct a bigger graph \cite{Di99}. This approach has been 
quite efficient in designing graphs with even number of vertices. For
example it does not apply to construction of graphs where the number of
vertices is a prime number. Another construction technique
\cite{HX07}, \cite{H07} involved the addition or deletion of a vertex in a known minimum 
broadcast graph. \cite{HX07} uses the vertex addition technique to 
design broadcast graphs on an odd number of vertices. 

\section{Hybrid Techniques}
So far we presented problems that either minimize the broadcast time 
in a given graph or minimize the number of edges provided that 
broadcasting can be completed within the theoretical minimum time. A 
third approach in broadcasting is the problem of considering the family of 
all graphs on 
$n$ vertices and $m$ edges and finding the least broadcast time a graph
can have and also constructing the graph which exhibits this behaviour. We call this problem 
the $(n,m)$ broadcast time optimization problem and $(n,m)$ graph 
construction problem. To the best of our knowledge the only result in 
this direction is the solution of the $(n,n-1)$ problem. In other words,
this is the problem of finding the minimum possible broadcast time in a
tree on $n$ vertices and the construction of such a tree. This result is 
due to Harutyunyan and Khachatrian \cite{Kh90} and Labahn \cite{RL89}.



%=============================================================================
\chapter{Unicyclic graphs}
In this chapter we continue the work of studying the broadcast time
on a specific class of graphs. In particualar we present a linear
algorithm , $O(|V|)$, that determines the broadcast time of
any originator in an arbitrary unicyclic graph
$G = (V, E)$. As a byproduct, we also find a broadcast center (a
vertex in $G$ with minimum broadcast time) of the unicyclic graph.
Using this algorithm we give a $O(|V|)$ algorithm to find the
broadcast time (maximum broadcast time) of an arbitrary unicyclic
graph. This algorithm, combined with the obvious lower bound,
gives a $\Theta(|V|)$ solution for the problem of determining the
broadcast time of an arbitrary unicyclic graph.
                                                                                                                                                                                 
A very important problem in this area is to find relationship
between the broadcast times of a connected graph $G=(V,E)$ and one
of its connected spanning subgraphs $H=(V,E')$. Such a result is
very useful for designing good approximation algorithms to
determine the broadcast time of an arbitrary vertex in an
arbitrary graph. This will also be used for finding or evaluating
the broadcast time of a given graph when the broadcast time of its
subgraph is known. As a first step in this direction we will give
tight lower and upper bounds on $b(H)$ expressed by $b(G)$. At the
end of this chapter we discuss the relation between the broadcast
times of a unicyclic graph and one of its spanning trees. We give
tight lower and upper bounds on broadcast time of a spanning tree
based on the broadcast time of the unicyclic graph.

\section{\bf Definitions and Auxiliary Results }
\label{sec:algo} A unicyclic graph (Fig. \ref {fig:unicyclic}) is
a connected graph with only one cycle. Basically it is a tree with
only one extra edge. It can also be seen as a cycle where every
vertex on the cycle is the root of a tree. Denote the vertices of
the cycle $C_k$ by $r_1,r_2,\cdots,r_k$ and the tree rooted at
$r_i$ by $T_i$, where $1 \leq i \leq k$. We will use the following
definitions and results from \cite{SCH81}.

\begin{figure}
\center
  \vspace {-12pt}
  % Requires \usepackage{graphicx}
  \includegraphics[scale = 0.6]{unicyclicgraph.eps}\\
  \caption{A unicyclic graph where the vertices $r_i$, belonging to the cycle $C_k$, are the
  roots of the trees $T_i$ for $1 \leq i \leq k$. }
  \label{fig:unicyclic}
  \vspace {+10pt}
\end{figure}

\

\begin {definition} [\cite{SCH81}]
The minimum broadcast time, $b(BC,G)$, of the graph $G=(V,E)$ is
defined to be the minimum of the broadcast times of all the
vertices. $b(BC,G)= min_{u \in V} \{b(u,G)\}$.
\end {definition}

\begin {definition} [\cite{SCH81}]
The broadcast center of the graph $G$, $BC(G)$, is defined to be
the set of all vertices whose broadcast time is equal to the
minimum broadcast time of the graph, $BC(G) = \{
u|b(u,G)=b(BC,G)\}$.
\end {definition}

\begin {theorem} [\cite{SCH81}]
\label {thm:minbrdcst} Let $v \notin BC(T)$ be a vertex in a tree
$T$ such that the shortest distance from $v$ to a vertex $x \in
BC(T)$ is $k$. Then $b(v,T) = k + b(BC,T)$.
\end {theorem}

\begin {corollary} [\cite{SCH81}]
\label {cor:star} For any tree T, BC(T) consists of a star with at
least two vertices.
\end {corollary}

The unicyclic graph can be converted into a tree by cutting one of
the edges of the cycle $C_k = r_1, r_2,..., r_k, r_1$. A simple
algorithm to determine the broadcast time of a vertex $w$ in an
arbitrary unicyclic graph $G=(V,E)$ would be the following:
\vspace {12pt}

 SIMPLEBROADCASTALGORITHM($w,G$):

\begin {enumerate}
\item Extract from $G$ the cycle $C_k$ and the trees $T_i$ for $1
\leq i \leq k$ which are rooted at a vertex on $C_k$.

\item Cut edge $(r_i, r_{i+1})$ from the cycle $C_k$, for
$i=1,2,...,k$. Denote the resulting tree by $G_i$.

\item Apply BROADCAST($w,G_i$) for $i=1,2,...,k$ from \cite{SCH81}
and choose the tree $G_i$ with the minimum broadcast time
$b(w,G_i)$.
\end {enumerate}

The complexity of step 1 of the algorithm is $O(n)$, where
$|V|=n$. The complexity of steps 2 and 3 are $O(k)$ and $O(kn)$
respectively. Thus, the total complexity of the above algorithm
will be $O(kn)$, which is $O(n^2)$ in the worst case. However,
$\Omega(n)$ is an obvious lower bound. In this paper we will show
$\Theta (n)$ bound by describing a linear algorithm that
determines the broadcast time of any vertex $w$ in an arbitrary
unicyclic graph.

\begin {notation}
If $u$ and $v$ are two vertices in graph $G$ then $(u,v)$
represents the edge between them, and $d(u,v)$ represents the
distance between them.
\end {notation}

\begin {definition}
\label {def:T12k} Given trees $T_1=(V_1,E_1)$, $T_2=(V_2,E_2)$,
$\cdots$, $T_i=(V_i,E_i)$ with roots $r_1$, $r_2$, $\cdots$, $r_i$
respectively, the  tree $T_{1,2,\cdots,i} =(V,E)$ = $T_1 \oplus
T_2 \oplus \cdots \oplus T_i$ is a tree where $V= V_1 \cup V_2
\cup \cdots \cup V_i$ and $E= E_1 \cup E_2 \cup \cdots \cup E_i
\cup \{ (r_1,r_2), (r_2,r_3), \cdots, (r_{i-1},r_i) \} $.
\end {definition}
In other words, the trees $T_i$ are connected by adding the edges
$(r_1,r_2)$, $(r_2,r_3)$, $\cdots$, $(r_{i-1},r_i)$.

\subsection{The broadcast center of the sum of two trees}
In this section we will describe how to find a broadcast center
and calculate the minimum broadcast time of the sum of two trees.
\begin {lemma}
\label {lem:SBC} In any tree $T$, rooted at $r$, there exists a
unique vertex $u \in BC(T)$, called the special broadcast center
denoted as $u = SBC(T)$, such that the path joining $u$ and $r$
does not contain any other vertex $v$ such that $v \in BC(T)$.
\end {lemma}

\begin {proof}
First we will show the existence of vertex $u$. Let $v$ be a
vertex such that $v \in BC(T)$ and let $P = v, v_1, v_2, \cdots,
v_k, r$ be
 the unique path from $v$ to $r$. Due to Corollary
\ref {cor:star} only $v_1$ can be in $BC(T)$. If $v_1 \in BC(T)$,
then it is the required vertex, and $v_1,v_2,\cdots,v_k,r$ is the
path from $SBC(T) = v_1$ to the root of $T$, $r$. If $v_1 \not\in
BC(T)$ then $v$ is the required vertex and $P = v, v_1, v_2,
\cdots, v_k, r$ is the unique path from $SBC(T) = v$ to the root
of $T$, $r$. The uniqueness of $u=SBC(T)$ immediately follows from
the fact that $T$ is a tree and no cycles are allowed in a tree.
\end {proof}

From Lemma \ref {lem:SBC} it follows that if $T_1$ and $T_2$ are
two trees with $u_1 = SBC (T_1)$ and $u_2 = SBC (T_2)$, then the
path that joins $u_1$ and $u_2$ does not contain any other vertex
$v$ (different than $u_1$ and $u_2$) such that $v \in (BC(T_1)
\cup BC(T_2))$.

In the remaining part of this section it is assumed that there are
two trees $T_1$ and $T_2$ with roots $r_1$ and $r_2$ respectively,
$T = T_1 \oplus T_2$, $u_1 = SBC(T_1)$, and $u_2 = SBC(T_2)$.

\begin{figure}
\center
  % Requires \usepackage{graphicx}
  \includegraphics[scale = 0.8]{trianglesum.eps}\\
  \caption{Sum of two trees.}\label{fig:trianglesum}
  \vspace {+10pt}
\end{figure}

\begin {theorem}
\label {thm:BCexist} There exists a vertex $u$ such that $u \in
BC(T_1 \oplus T_2)$ and $u$ is on the path joining $u_1 =
SBC(T_1)$ and $u_2 = SBC(T_2)$.
\end {theorem}
\begin {proof}
We will prove this theorem by contradiction. Assume that there
exists a vertex $x'$ (Fig. \ref {fig:trianglesum}) not on the path
from $u_1$ to $u_2$ and such that $b(x',T) < b(u,T)$ for all
vertices $u$ on the path joining $u_1$ and $u_2$. Without loss of
generality assume that $x'$ is in $T_1$. Because $T$ is a tree,
there exists a unique path $P$ that joins $x'$ to $r_1$. Two cases
may arise:

{\em Case 1}: The path $P$ intersects the path from $u_1$ to $r_1$
at a vertex other than $u_1$. Let $u \in P$ be this intersection
vertex. We denote by $t_1(x)$ the minimum time that is needed to
inform all the vertices of $T_1$ starting at the originator $x$.
Therefore, $b(u,T_1) = t_1(u) = d(u,u_1) + b(BC,T_1)$ and $t_1(x')
= b(x',T_1)= d(x',u) + (d(u,u_1) + b(BC,T_1))=d(x',u)+ t_1(u)$.
Similarly, the minimum time to inform all the vertices in $T_2$
starting at any originator $x$ will be denoted by $t_2(x)$. We
have $t_2(u) = d(u,r_1)+1 +d(r_2,u_2) + b(BC,T_2) = d(u,u_2) +
b(BC,T_2)$ and $t_2(x') = d(x',u) + d(u,u_2) + b(BC,T_2)$. Having
calculated $t_1(x)$ and $t_2(x)$ we can calculate $b(x,T)$ since
$b(x,T) = t_1(x) + 1$ if $t_1(x)= t_2(x)$ and $b(x,T) = max \{
t_1(x),t_2(x)\}$ otherwise. Since, $t_1(x') >  t_1(u)$ and
$t_2(x') t_1(u)$ we conclude that $b(x',T) > b(u,T)$ which
contradicts the assumption that $b(x',T) < b(u,T)$. {\em Case 2}:
The path $P$, joining $x'$ and $r_1$, does not intersect the path
joining $u_1$ and $r_1$. In this case the path $P$ will merge with
the path joining $u_1$ and $r_1$ at vertex $u_1$. Consider
$t_1(x')=d(x',u_i)+t_1(u_1)$, where $u_i \in BC(T_1)$. $u_i$ can
be either $u_1$ or one of its neighbors since the broadcast center
of a tree is a star [\cite{SCH81}]. So we can write $t_1(x') = k +
t(u_1,T_1)$ where $k \geq 0$ is a the distance $d(x',u_i)$.
Similarly, $t_2(x') = d(x',u_i)+ d(u_i,u_2) + b(BC,T_2)$. It can
also be written as $t_2(x') = k + delta + d(u_1,u_2) + b(BC,T_2)$,
which is equal to $t_2(x') = k + \delta + t_2(u_1)$ where $\delta
= 0$ if $u_i = u_1$ and $\delta = 1$ if $u_i$ is a neighbor of
$u_1$. Therefore, we can see that if $t_2(x') \geq t_1(x')$ it
also implies that $t_2(u_1) > t_1(u_1)$ and since $t_2(x') >
t_2(u_1)$ then $b(x',T) > b(u_1,T)$ which is a contradiction.
Similarly if $t_1(x') > t_2(x')$ then we can conclude that
$t_1(u_1)\geq t_2(u_1)$ and together with the fact that $t_1(u_1)
< t_1(x')$ we conclude that $b(u_1,T) \leq b(x',T)$ which is again
a contradiction. \footnote {Refer to Fig. \ref {fig:sumexample}
for an example illustrating Theorems \ref {thm:BCexist} and \ref
{thm:BCdist}.}
\end {proof}

Let $u$ be a vertex such that $u \in BC(T_1 \oplus T_2)$. Theorem
\ref {thm:BCexist} confirms the existence of such a vertex on the
path joining $u_1$ and $u_2$. The position of $u$ can be found as
described in the following theorem. Note that \cite{HM07} presents
a partial proof of the theorem below. Here we present a complete
proof.

\begin {theorem}
\label {thm:BCdist} Let $A = b(BC,T_1) - b(BC,T_2)$ and $B =
d(r_1,u_1) + d(r_2,u_2) + 1$. Three cases may arise:

If $B-A<0$, then $d(u,u_1) = 0$, i.e. $u$ coincides with $u_1$.

If $A+B<0$, then $d(u,u_1) = B$, i.e. $u$ coincides with $u_2$.

If $B-A \geq 0$ and $A+B \geq 0$, then $d(u,u_1) = \lfloor \frac
{B - A}{2} \rfloor$ or $d(u,u_1) = \lceil \frac {B - A}{2}
\rceil$. Both positions of $u$ have equal broadcast times in the
tree $T$.
\end {theorem}

\begin {proof}
If $B-A < 0$, then we have

\begin {equation}
\label {eq:cond1} b(BC,T_1) > b(BC,T_2) + d(u_1,r_1) + 1 +
d(u_2,r_2).
\end {equation}

We will prove that $u = u_1 \in BC(T)$ by contradiction. Assume
that there is another vertex $u'$ on the path joining $u_1$ and
$u_2$ such that $b(u',T) < b(u,T)$. Because of Theorem \ref
{thm:BCexist} we do not have to consider a vertex not belonging to
the path joining $u_1$ and $u_2$. Using the definitions of the
functions $t_1(x)$ and $t_2(x)$ from above we get: $t_1(u') =
d(u',u_1) + b(BC,T_1)$, $t_2(u') = d(u',r_1)+ 1 + d(u_2,r_2) +
b(BC,T_2)$, $t_1(u) = b(BC,T_1)$, and $t_2(u) = d(u_1,r_1) + 1 +
d(u_2,r_2) + b(BC,T_2)$. Using the condition in equation \ref
{eq:cond1} we get that $t_1(u) = b(BC,T_1) > t_2(u) = d(u_1,r_1) +
1 + d(u_2,r_2) + b(BC,T_2)$ Therefore, $b(u,T) = t_1(u)$.
Similarly, $t_1(u') = d(u',u_1) + b(BC,T_1)$ $> d(u',u_1) +
b(BC,T_2) + d(u_1,r_1) + 1 + d(u_2,r_2)$ which implies that
$t_1(u') d(u',u_1) + b(BC,T_2) + d(u_1,u') + d(u',r_1) + 1 +
d(u_2,r_2) = 2d(u',u_1) + b(BC,T_2) + d(u',r_1) + 1 + d(u_2,r_2) =
2d(u',u_1) + t_2(u')$ which implies that $t_1(u') > t_2(u')$ and
hence $b(u',T) = t_1(u')$. But we have $t_1(u') = d(u',u_1) +
b(BC,T_1)$ and $t_1(u) = b(BC,T_1)$ which implies that $t_1(u') >
t_1(u)$. Therefore we conclude that $b(u',T) b(u,T)$ which
contradicts the assumption. The case $A+B<0$ can be proved
similarly.

Note that the two conditions $A+B<0$ and $B-A<0$ are mutually
exclusive. If either one of them is satisfied the other will not
be satisfied. The only remaining case is when both of them are not
satisfied i.e. $A+B \geq 0$ and $B-A \geq 0$. Assume the case
where $B-A$ is odd, the case if it is even can be dealt with
similarly. Without loss of generality, assume that there exists a
vertex $u' \in T_1$, on the path joining $u_1$ and $u_2$, such
that $b(u',T) < b(u,T)$. Two cases may arise:

{\em Case 1}: $d(u',u_1) < d(u,u_1) = \lfloor \frac {B - A}{2}
\rfloor$. Since $B-A$ is assumed to be odd, $d(u,u_1) = \frac {B -
A - 1}{2}$. Calculating $t_1(u) = d(u,u_1) + b(BC,T_1)$ and
$t_2(u) = d(u,r_1) + 1 + d(u_2,r_2) + b(BC,T_2)$ we deduce that
$t_2(u) = (d(u_1,r_1) - d(u,u_1)) + 1 + d(u_2,r_2) + b(BC,T_2)$.
Substituting the value of $d(u,u_1)$, and $b(BC,T_2) =
b(BC,T_1)-A$ we get: $t_2(u) = [d(u_1,r_1) + 1 + d(u_2,r_2)] +
b(BC,T_2) - d(u,u_1) = B + (b(BC,T_1)-A) - \frac {B - A - 1}{2}$
$= \frac {B-A+1}{2} + b(BC,T_1) = t_1(u) +1$. Therefore, $b(u,T) =
t_2(u)$. Now consider the vertex $u'$, $t_1(u') = d(u',u_1) +
b(BC,T_1)$ and $t_2(u') = d(u',u) + d(u,r_1) + 1 + d(u_2,r_2) +
b(BC,T_2)$. Since $d(u',u_1) < d(u,u_1)$, we get $t_1(u') <
t_1(u)$. Moreover, $t_2(u') = d(u',u) + t_2(u) > t_1(u')$ since
$t_2(u) > t_1(u) t_1(u')$. Finally we get $b(u',T)=t_2(u')>b(u,T)$
which contradicts the assumption. {\em Case 2}: $d(u',u_1) >
d(u,u_1)$. As it was done in the previous case, we can deduce that
$t_2(u)=t_1(u)+1$ and $b(u,T) = t_2(u)$. Now consider the vertex
$u'$. Calculating $t_1(u')$ and $t_2(u')$ we get:
$t_1(u')=d(u',u)+d(u,u_1)+b(BC,T_1)$ and $t_2(u')=
d(u',r_1)+1+d(r_2,u_2)+b(BC,T_2)$. Using that $d(u,r_1) = d(u,u')
+ d(u',r_1)$ we get that $t_2(u')=
[d(u,r_1)-d(u,u')]+1+d(r_2,u_2)+b(BC,T_2)$. Hence, $t_2(u')=
t_2(u)-d(u,u')=t_1(u)+1-d(u,u')$. On the other hand, $t_1(u')=
t_1(u)+d(u,u')$. Since $d(u',u_1) > d(u,u_1)$, we conclude that
$d(u,u') \geq 1$. Subtracting $t_2(u')$ from $t_1(u')$ we get:
$t_1(u') - t_2(u') = t_1(u)+d(u,u') - [t_1(u)+1-d(u,u')]$.
Therefore, $t_1(u') - t_2(u') = 2d(u,u') - 1$. Using $d(u,u') \geq
1$, we get that $t_1(u') > t_2(u')+1$. Hence, we conclude that
$b(u',T) = t_1(u')$. So, $b(u',T) = t_1(u') = t_2(u') + 2d(u,u') -
1$. Furthermore, using $t_2(u') = t_2(u) -d(u,u')$ we get
$b(u',T)= t_2(u) + d(u,u') - 1 \geq t_2(u)$, which implies that
$b(u',T) \geq b(u,T)$ a contradiction.
\end {proof}

\begin{figure}
\center
  % Requires \usepackage{graphicx}
  \includegraphics[scale = 1]{sumexample}\\
  \caption{An example of the sum of two trees. It shows
  the vertices in the broadcast center and the special broadcast center
  of $T_1$, $T_2$, and $T_1 \oplus T_2$. The minimum
  broadcast time of the three trees are calculated too.}
  \label{fig:sumexample}
  \vspace {+10pt}
\end{figure}

\section{The UNICYCLICBROADCAST Algorithm}

The algorithm, $UNICYCLICBROADCAST(w,G)$, calculates the broadcast
time, $b(w,G)$, of a given vertex $w$ in any unicyclic graph $G$.
For convenience we will assume that $w$ belongs to tree $T_1$.

\subsection{Description of the Algorithm}
INPUT: A unicyclic graph $G$ on $n$ vertices and the broadcast
originator $w$.

\noindent OUTPUT: Broadcast time of the originator $w$ in $G$,
$b(w,G)$, and a broadcast scheme.

\vspace {12pt} \noindent UNICYCLICBROADCAST($w,G$):

\begin {enumerate}
\item Extract from $G$ the cycle $C_k$, consisting of the vertices
$\{r_1,r_2,\cdots,r_k\}$, and the trees $T_i$ rooted at the
vertices $r_i$ for $1 \leq i \leq k$.

\item For all trees $T_i$  where $1 \leq i \leq k$ calculate and
save the positions of $u_i=SBC(T_i)$ relative to $r_i$, as well as
$b(BC,T_i)$.

\item Calculate and save the distance $d(w,u_1)$ and the path
joining $w$ and $u_1$.

\item Construct the trees $T_{1,2,\cdots,i}$, where $2 \leq i \leq
k$, and $T_{k,k-1,\cdots, i}$, where $1 \leq i \leq k-1$. For each
tree $T$, compute and store the position of the $SBC(T)$ and
$b(BC,T)$.

\item Construct the spanning trees
$T_{j,j+1,\cdots,k,1,2,\cdots,j-1}$, where $1 \leq j \leq k$. For
each tree $T$ compute and store $SBC(T)$, $b(BC,T)$,
$d(w,SBC(T))$, and $b(w,T)$.

\item Out of the trees generated in the previous step, choose the
spanning tree $T$ with the minimum value of $b(w,T)$.

\item Run BROADCAST \cite{SCH81} to find a broadcast scheme for
the originator $w$.
\end {enumerate}

The algorithm first preprocesses the unicyclic graph and
calculates the cycle $C_k$ consisting of the vertices
$\{r_1,r_2,\cdots,r_k\}$ and the trees $T_i$ rooted at $r_i$ ,
where $1 \leq i \leq k$. In step 2 the path joining $w$ to $u_1$
and $d(w,u_1)$ are calculated and saved. This information will be
needed to calculate the broadcast time of $w$. Steps 3 and 4
construct several trees and calculate results that will be used in
constructing the $k$ spanning trees of the graph $G$. More
specifically the trees, $T_i$, $T_{i,i+1,\cdots, k}$ for $1 \leq i
\leq k-1$, and $T_{1,2, \cdots, i}$ for $2 \leq i \leq k$ are
constructed. For each spanning tree $T$ the position of the
$SBC(T)$ and $b(BC,T)$ are calculated and stored. These results
will be useful to calculate the broadcast centers and the minimum
broadcast times of the spanning trees. At the end of step 4 only
one spanning tree will be constructed. In step 5, the algorithm
builds the remaining $k-1$ spanning trees of the unicyclic graph.
It also calculates the broadcast time of $w$ for each one of them.
Note that for each spanning tree $T$, $b(w,T) =
d(w,SBC(T))+b(BC,T)$ where the distance $d(w,SBC(T)$ can be easily
calculated by using $d(w,u_1)$ and position of $SBC(T)$ calculated
in steps $2$ and $4$ respectively. The spanning tree that has the
minimum broadcast time for $w$ is the required result. Finally in
order to obtain the optimal broadcast scheme for the originator
$w$ in the unicyclic graph $G$, the BROADCAST algorithm of \cite
{SCH81} is run on the spanning tree $T$ that had the minimum value
of $b(w,T)$.

In step 5, $k-1$ spanning trees are constructed each in a constant
time. The construction of each tree can be done easily by
observing that the spanning tree $T_{i,i+1, \cdots,k,1,2, \cdots,
i-1}$ is the sum of the two trees $T_{i,i+1,\cdots,k}$ and
$T_{1,2,\cdots,i-1}$ rooted at $r_k$ and $r_1$ respectively. These
two trees and all the information pertinent to the calculation of
the $b(w,T_{i,i+1, \cdots,k,1,2, \cdots, i-1})$ were calculated in
step 4.

\subsection{Proof of Correctness and Complexity Analysis}

\begin {theorem}
$UNICYCLICBROADCAST(w,G)$ generates a broadcast scheme for
originator $w$, and finds $b(w,G)$.
\end {theorem}
\begin {proof}
Let $C_k$, consisting of the vertices $\{ r_1, r_2, \cdots, r_k
\}$, represent the cycle in the unicyclic graph $G$. One of the
spanning trees of $G$ is obtained by removing the edge
$(r_k,r_1)$. The resulting tree is $T_{1,2,\cdots, k}$. The
minimum broadcast time of $T_{1,2,\cdots, k}$ is calculated
iteratively by tree summations $T_{1,\cdots,i-1} \oplus T_i$
rooted at $r_{i-1}$ and $r_i$ respectively, where $2 \leq i \leq
k$. The remaining minimum spanning trees,
$T_{j,j+1,\cdots,k,1,2,\cdots,j-1}$ where $2 \leq j \leq k$, are
calculated by performing the summations $T_{j,\cdots,k} \oplus
T_{1,\cdots,j-1}$. Theorems \ref {thm:BCexist} and \ref
{thm:BCdist} guarantee that a broadcast center and the minimum
broadcast time of all the trees
$T_{j,j+1,\cdots,k,1,2,\cdots,j-1}$, where $1 \leq j \leq k$, are
calculated correctly. Since, the trees
$T_{j,j+1,\cdots,k,1,2,\cdots,j-1}$, where  $1 \leq j \leq k$, are
the all possible spanning trees of the unicyclic graph $G$, the
algorithm correctly finds the spanning tree of the unicyclic graph
$G$ that has the minimum broadcast time of all the spanning trees.
We will prove the correctness of the algorithm by contradiction.
Assume that there exists a broadcast tree $T'$ and a broadcast
scheme in $G$ that performs broadcasting in time $t$ such that $t
= d(w,BC(T')) + b(BC,T')< b(w,G)$. $T'$ should be one of the trees
$T_{j,j+1,\cdots,k,1,2,\cdots,j-1}$, where  $1 \leq j \leq k$. But
the algorithm correctly calculated the minimum broadcast time of
all the spanning trees and chose the spanning tree $T$ with the
minimum value of $d(w,BC(T)) + b(BC,T)$. Therefore the existence
of $T'$ creates a contradiction.
\end {proof}

\begin {theorem}
The complexity of the UNICYCLICBROADCAST running on a unicyclic
graph $G=(V,E)$ is $O(|V|)$.
\end {theorem}
\begin {proof}
Steps 1 and 2 of the algorithm can be accomplished by a depth
first search in $O(|V|)$ time. In Step 3, BROADCAST \cite{SCH81}
is applied on the trees $T_i$ for $1 \leq i \leq k$. The
complexity of this step is $O(|V_1| + |V_2| + \cdots + |V_k|)$
$=O(|V|)$. Step 4 is of complexity $O(k)$ since there are $k$ sums
to be done, and the sum of two trees $T_1$ and $T_2$, $T_1 \oplus
T_2$, can be done in a constant time. Moreover, every time a tree
$T$ is constructed as $T=T_1 \oplus T_2$, calculating the distance
between the root of $T$ and $SBC(T)$, and $b(BC,T)$ can be done in
a constant time using the positions of $SBC(T_1)$ and $SBC(T_2)$,
and the broadcast times $b(BC,T_1)$ and $b(BC,T_2)$. Step $5$
involves the calculation of $k-1$ spanning trees. Each spanning
tree is constructed by summing two trees, hence the complexity of
this step is again $O(k)$. Step 6 chooses the spanning tree with
the least minimum broadcast time hence its complexity is $O(k)$.
Adding all the complexities we get that the complexity of the
algorithm is $O(|V|+k)$. However, $k \leq |V|$, so this proves
that the complexity of the algorithm UNICYCLICBRDCST is $O(|V|)$.
\end {proof}


\section {\textbf{The Broadcast Time of a Unicyclic Graph}}
So far, we showed how to calcuate the minimum broadcast time of a
unicyclic graph and how to caluclate the broadcast time of a
vertex in the unicyclic graph. The main problem which is usually
studied in the literature concerns finding $b(G)$, the broadcast
time of the given graph $G$. There is an obvious algorithm that
will run in $kO(n) = O(kn)$ time. In this section we will present
an algorithm to calculate the broadcast time of an arbitrary
unicyclic graph in $O(n+k^2)$ time. This is always better than the
$O(kn)$ algorithm except when $k = \Theta(|V|)$. In particular,
our algorithm is linear of $|V|$ when $k = O(\sqrt(|V|)$.

For a vertex $v$ in a graph $G$ assume that $u \in BC(G)$ is the
closest vertex to $v$. In general, the broadcast tree of the
optimum broadcast scheme of vertex $v$ is not the same as the
broadcast tree of the optimum broadcast scheme of $u$. Hence,
calculating the broadcast center of the graph and then finding the
furthest vertex from the broadcast center does not guarantee that
the sum of that distance and the minimum broadcast time is the
broadcast time of the graph $G$.

The major modification of the algorithm will involve calculating
the broadcast time of each spanning tree
$T_{i,\cdots,k,1,\cdots,\i-1}$. The modified UNICYCLICBROADCAST
algorithm is presented below:

\noindent UNICYCLICBROADCAST($G$):

\begin {enumerate}
\item Extract from $G$ the cycle $C_k$, consisting of the vertices
$\{r_1,r_2,\cdots,r_k\}$, and the trees $T_i$ rooted at the
vertices $r_i$ for $1 \leq i \leq k$.

\item For all trees $T_i$  where $1 \leq i \leq k$ calculate and
save the positions of $u_i=SBC(T_i)$ relative to $r_i$, as well as
$b(BC,T_i)$ and the vertex $v_i$ such the $d(r_i,v_i)$ is maximum.

\item Construct the trees $T_{1,2,\cdots,i}$, where $2 \leq i \leq
k$, and $T_{k,k-1,\cdots, i}$, where $1 \leq i \leq k-1$. For each
tree $T$, compute and store the position of the $SBC(T)$ and
$b(BC,T)$.

\item Construct the spanning trees
$T_{j,j+1,\cdots,k,1,2,\cdots,j-1}$, where $1 \leq j \leq k$. For
each tree $T$ compute and store: $SBC(T)$, $b(BC,T)$,
$d(w,SBC(T))$, $b(w,T)$, and the broadcast time of $b(T)$

\item Out of the trees generated in the previous step, choose the
spanning tree $T$ with the minimum value of $b(T)$.

\end {enumerate}

Step 4 of the above algorithm is the main place where the major
modification was done. The additional value that is being
calculated is the broadcast time of each spanning tree $T$. This
calcluation can be done in $O(k)$ time as follows. Assume that the
$SBC(T)$ is in tree $T_n$. Calculate the quanties $d(SBC(T),r_n) +
d(r_n,r_j) + d(r_j,v_j)$ for $1 \leq j \leq k$ and $i \neq j$.
Also calculate the distance $d(SBC(T), SBC(T_n))$. Choose the
maximum of these values, $d_{max}$. This way we calculated the
furthest distance from $SBC(T)$, hence, $b(T) = d_{max} +
b(BC,T)$.

\begin {theorem}
The algorithm UNICYCLICBROADCAST($G$) calculates $b(G)$ in $O(|V|+
k^2)$ time.
\end {theorem}

\begin {proof}
Step 1 of the algorithm needs $O(|V|)$ time. Steps 2 and 3 take
$O(k)$ time as it was argued previously. The difference from the
previous algorithm lies in step 4 which is not constant time
operation anymore. For each spanning tree $T$, calculating $b(T)$
involves calculating $k$ distances and finding the minimum. This
needs $O(k)$ steps. Hence, the complexity of this step is
$O(k^2)$. Step 5 has complexity $O(k)$. Therefore, we conclude
that the complexity of the algorithm is $O(n + k^2)$.
\end {proof}




\section{Lower and Upper Bounds on the Broadcast Time of Unicyclic Graph}

A very important problem in this area is to find relationship
between the broadcast times of a connected graph $G=(V,E)$ and one
of its connected spanning subgraphs $H=(V,E')$. Such a result is
very useful for designing good approximation algorithms to
determine the broadcast time of an arbitrary vertex in an
arbitrary graph. This will also be used for finding or evaluating
the broadcast time of a given graph when the broadcast time of its
subgraph is known. As a first step in this direction we will give
tight lower and upper bounds on $b(H)$ expressed by $b(G)$, where
$G$ is an arbitrary unicyclic graph.

%Let $G=(V,E)$ be a unicyclic graph and $H=(V',E')$ be a
%vertex-induced subgraph of $G$which was obtained after deleting
%vertex $v$ from $G$ with all its incident edges. If $H=(V',E')$ is
%a unicyclic graph then $v$ obviously was a leaf the deleted vertex
%$b(H) \leq b(G) \leq b(H) + 1$

%It is clear that any connected vertex-induced subgraph of a given
%unicyclic graph is either a tree or a unicyclic graph

\subsection{Lower and Upper Bounds on the Minimum Broadcast Time}
The result obtained in this section will be used in section 5.2 to
give tight lower and upper bounds on the broadcast time of a
spanning tree of a unicyclic graph $G=(V,E)$. In this section we
will study how much does the minimum broadcast time (the broadcast
time of the broadcast center) of a unicyclic graph vary when
different edges of the cycle are broken (one at a time). First it
is obvious that if the cut edge is not from the cycle then we will
end up with two disconnected components. So our interest is to see
how high the minimum broadcast time of unicyclic graph can be
compared to the minimum possible value.

It is clear that deleting an edge (or edges) from a graph will
increase the minimum (or maximum) broadcast time of the initial
graph. The bounds that we are looking at do not necessarily happen
in all unicyclic graphs. For example when the trees attached to
the cycle are isomorphic then it will not make any difference
whichever edge was broken. Thus, it remains to give an upper bound
on the minimum broadcast time of the worst spanning tree of the
unicyclic graph.

%We want to study the worst case scenario of a unicyclic graph
%where cutting the wrong edge increases the broadcast time to the
%maximum possible. In other words, we want to find out the relation
%of the maximum compared to the minimum value.

Let $G=(V,E)$ be a unicyclic graph. The $k$ vertices of the cycle
are denoted by $r_i$ where $1 \leq i \leq k$, without loss of
generality assume that removing the edge $(r_1,r_k)$ yields the
tree $T = T_{1,\cdots,k}$ with the minimum broadcast time
$t_{min}$. In other words $b(BC,G) = b(BC,T) = t_{min}$. Now
assume that the edge $(r_1,r_k)$ is restored and another edge
$(r_i,r_{i+1})$ is broken. The broadcast time of the resulting
tree can be calculated by noticing that the tree
$T'=T_{i+1,i+1,\cdots,k,1,2,\cdots,i}$ is the sum of the two trees
$T_1= T_{i+1,\cdots,k}$ and $T_2=T_{1,\cdots,i}$. One important
factor that decides the broadcast time of $T'$ is the distance
between the special broadcast centers of $T_1$ and $T_2$.

To calculate the broadcast time of $T_{1,\cdots,k}$,
$b(T_{1,\cdots,k})=t_{min}$ by using the two trees
$T_1=T_{1,\cdots,i}$ and $T_2= T_{i+1,\cdots,k}$ we use Theorem 3.

To apply theorem 3, we need to consider that the tree $T_1$ is
rooted at $r_i$ and $T_2$ is rooted at $r_{i+1}$. Assume that
$SBC(T_1)$ is in the tree rooted at $r_x$ and $SBC(T_2)$ is in the
tree rooted at $r_{y}$. Let $t_1$ and $t_2$ be the broadcast time
of $SBC(T_1)$ in $T_1$ and $SBC(T_2)$ in $T_2$ respectively. Let
$d_x$ be the distance between $SBC(T_1)$ and  $r_x$ and $d_y$ be
the distance between $SBC(T_2)$ and  $r_y$. We directly apply
theorem 3 to find the broadcast centers of $T$. Direct
substitution gives:

$A = b(BC,T_1) - b(BC,T_2)$ and $B = d_x + d_y + y - x$.

And the two possible vertices, $u$ and $u'$, of the broadcast
center of $T$ are at the following distance from $SBC(T_1)$:

$\lfloor \frac {B - A}{2} \rfloor$ and $\lceil \frac {B - A}{2}
\rceil$.

Note that Theorem 3 has three different cases, however the first
two cases lead to the situation when the new broadcast center
coincides with one of the broadcast centers of the initial trees.
It easy to verify (the details are omitted) that these two cases
do not lead to an upper bound that we are looking for. So, we
assume that case 3 of Theorem 3 holds.

Now we calculate the broadcast time of $T' =
SBC(T_{i,i+1,\cdots,k,1,2,\cdots,i})$ again using the same trees
$T_1$ and $T_2$. Doing this we will allow us to compare $b(BC,T)$
and $b(BC,T')$  because they will be represented in terms of the
same variables. Again using theorem 3 we can find the vertices of
the broadcast center. Here, we need to assume that $T_1$ is rooted
at vertex $r_1$ and $T_2$ is rooted at vertex $r_k$. However, this
does not change the previous assumption that $SBC(T_1)$ is in
$T_1$ and $SBC(T_2)$ is in $T_2$. Direct application of theorem 3
gives:

$A' = b(BC,T_1) - b(BC,T_2)$ and $B' = d_x + d_y + k - (y - x)$.

The two possible vertices, $u$ and $u'$, of the broadcast center
of $T'$ are at the following distance from $SBC(T_1)$:

$\lfloor \frac {B' - A'}{2} \rfloor$ and $\lceil \frac {B' -
A'}{2} \rceil$.

After finding the vertices of the broadcast center one can easily
calculate the minimum broadcast time. There are two cases that one
has to consider. One case is when $B-A$ is odd and the other when
it is even. In the first case there will be two vertices in the
broadcast center and in the latter case there will be one vertex
only.

\noindent $t_{min} = b(BC,T) = \frac{B-A}{2} + t_1 + 1$ when $B-A$
is even.

\noindent $t_{min} = b(BC,T) = \lceil \frac {B-A}{2} \rceil + t_1$
when $B-A$ is odd.

Rewriting the two equations we get:

\noindent  $t_{min} = b(BC,T) = \frac{t_1 + t_2 + d_x + d_y + y -
x + 2}{2}$ when $B-A$ is even.

\noindent $t_{min} = b(BC,T) = \frac{t_1 + t_2 + d_x + d_y + y - x
+ 1}{2}$ when $B-A$ is odd.

Similarly the broadcast time of $T'$ can be obtained:

\noindent  $b(BC,T') = \frac{t_1 + t_2 + d_x + d_y + k - (y - x) +
2}{2}$ when $B'-A'$ is even.

\noindent $b(BC,T') = \frac{t_1 + t_2 + d_x + d_y + k - (y - x) +
1}{2}$ when $B'-A'$ is odd.

We have $4$ combinations of the parity of $B-A$ and $B' - A'$. To
calculate the upper bound on minimum broadcast time each
combination has to be treated separately. Assume the case where
$B-A$ is odd and $B'-A'$ is even. All other cases can be handled
similarly. in this case we get the following: $b(BC,T') =
\frac{2t_{min}+ 2(x-y) + k + 1}{2}$.

The broadcast time depends on two variables: $(x-y)$ and $k$. To
maximize $b(BC,T')$, the minimum broadcast time of $T'$ we need to
maximize $2(x-y) + k$. By definition of $x$ and $y$ it follows
that $(x-y) \leq -1$. Assume that $x-y = -1$. Finding the maximum
value of $k$ needs more careful observation.

An upper bound on $k$ can be obtained by considering the cycle
alone. We know that the broadcast time of a cycle of size $k$ is
$\lceil \frac{k}{2} \rceil$, hence $t_min \geq \lceil \frac{k}{2}
\rceil$. In other words, $k \leq 2t_{min}$ when $k$ is even and $k
\leq 2t_{min} - 1$ when $k$ is odd. now we will show that the last
suggested upper bound on $k$ cannot be attained. Without loss of
generality assume that $k$ is even and $k=2t_{min}$. When $k$ is
odd by similar calculations we can arrive to the same result, so
why we omit this case. The broadcast centers of the $T$ should be
$r_1$ and/or $r_k$ because we know that $x-y = -1$. Since
$b(BC,T')$ is maximum, then the broadcast time, $t$, of $r_1$ in
$T_1$, the tree attached to the cycle at $r_1$ should be equal to
the broadcast time of $r_k$ in $T_k$, the tree attached to the
cycle at $r_k$. Moreover, there should be one path both in $T_1$
and $T_k$ of length $t$. Now consider the optimum broadcast scheme
of $r_1$ in $T$. First $r_1$ should inform $r_k$, then $r_1$ and
$r_k$ should inform their neighboring vertices on the cycle.
Otherwise, the vertices of the cycle will not be informed by the
time $t_{min}$. Then during the third time unit, $r_1$ and $r_k$
can start informing the vertices of $T_1$ and $T_k$ respectively.
This means $b(r_1,T_1) \leq t_{min} - 2$ and $b(r_k,T_k) \leq
t_{min} - 2$. Hence the longest path in the graph $T'$ can be
$4t_{min} - 4$ and $b(T') \leq 2t_{min} - 2$. This construction
shows that if $x-y = -1$ then $k = 2T_{min} - 2$ (by our
assumption $k$ is even). Thus, $2(x-y) + k \leq 2T_{min} - 4$
which leads to $b(BC,T') \leq \frac{4t_{min} - 3}{2} = 2T_{min} -
2$.

Therefore, in the case of $B-A$ is odd and $B'-A'$ is even, the
maximum value of $b(BC,T')$ can be $b(BC,T') \leq 2t_{min}- 2$.
Note that $B-A$ being odd and $B'-A'$ even implies that $k$ is
odd. It should be noted that the remaining combinations of the
parity of $B-A$ and $B'-A'$ either result in the same upper bound.

Actually we proved the following result:

\begin{theorem}
If $G$ is a unicyclic graph and $T'$ is a spanning tree of $G$
then $b(BC,G) \leq b(BC,T') \leq 2b(BC,G) - 2$.
\end{theorem}

In figure 4 we present an example of a unicyclic graph where
$b(BC,T') \leq 2t_{min}- 2$. Figure 4c presents $T'$, where
$b(BC,T') = \max\{b(BC,P) | P$ is a spanning tree of unicyclic
graph $G\} = 8$. Figure 4b shows the spanning tree $T$ for which
$b(BC,G) = b(BC,T) = 5$. Figure 4 presents graphs on $n$ vertices
for which $b(BC,T') = 2b(BC,G) - 2$, for any $n = 0 (\mod 4)$.

\begin{figure}
\center
  \vspace {-10pt}
  % Requires \usepackage{graphicx}
  \includegraphics[width=5in, height= 4in]{example.eps}\\
  \caption{a: Shows the unicyclic graph that can have the maximum variation in the minimum broadcast time depending on
  which edge gets cut. b: Shows the graph with the best edge removed and whose minimum broadcast time is 5 and is the minimum value possible.
  c: Show the graph with the wrong edge removed where the minimum broadcast time increases to 8. }
  \label{fig:example}
  \vspace {+10pt}
\end{figure}


\subsection{Lower and Upper bounds Bounds on Broadcast Time}

In this section we will give tight lower and upper bounds on the
broadcast time of a spanning tree $T'=(V,E')$ of a unicyclic graph
$G=(V,E)$ expressed by $b(G)$, the broadcast time of unicyclic
graph $G$.

\begin{theorem}
If $G$ is a unicyclic graph and $T'$ is a spanning tree of $G$
then $b(G) \leq b(T') \leq 2b(G) - 21$.
\end{theorem}

\begin{proof}
To prove the lower bound consider unicyclic graph $G$ that
contains cycle of length $3$ and a path of length $n - 3$ starting
from one of the vertices of the cycle. It is clear that
broadcasting from  the leaf of the cycle takes $n-1$ time units,
so $b(G) = n - 1$. It is obvious that $b(T') = b(G) = n - 1$ for
any spanning tree of $G$.

To prove the upper bound we will use the upper bound from Theorem
7. Consider any spanning tree $T'$ of a unicyclic graph $G$. We
know that $b(T') = b(BC,T') + d_{max}^{T'}$, where $d_{max}^{T'}$
is the maximum distance from a vertex, denote it by $v$, to the
nearest vertex in broadcast center, denote it by $u'$, of tree
$T'$. The broadcast scheme of a vertex in unicyclic graph that
gives $b(G)$ belongs to a spanning tree of $G$. Denote it by $T$.
As above, $b(G) = b(T) = b(BC,T) + d_{max}^{T}$, where
$d_{max}^{T}$ is the maximum distance from a vertex to the nearest
vertex in the broadcast center (denote it by $u$) of tree $T$.
Consider broadcasting from originator $v$ in spanning tree $T$. To
broadcast from $v$ in $T$ vertex $v$ first must inform the
vertices of the path to vertex $u$ or its neighbor which also
belongs to $(BC,T)$. We can show that $dist(v,u')$ in tree $T'$ is
at most $\lceil \frac{k}{2} \rceil + dist(v,u)$ where $dist(v,u)$
is calculated in tree $T$. So, $dist(v,u') = d_{max}^{T'} \leq
\lceil \frac{k}{2} \rceil + d_{max}^{T}$. Considering that $\lceil
 \frac{k}{2} \rceil \leq d_{max}^{T}$ from above we get that
$d_{max}^{T'} \leq 2d_{max}^{T} + 1$. Using this last bound from
$b(T') = b(BC,T') + d_{max}^{T'}$ we get that $b(T') = \leq
b(BC,T') + 2d_{max}^{T} + 1$. From Theorem 7 we have that
$b(BC,T') \leq 2b(BC,G) - 2$ for any spanning tree $T'$. Therefore
from above we get that $b(T') = \leq b(BC,T') + 2d_{max}^{T} + 1
\leq 2b(BC,G) - 2 + 2d_{max}^{T} + 1 = 2(b(BC,G) + d_{max}^{T}) -
1 = 2b(G) - 1$.
\end{proof}

The upper bound from this theorem is also attainable. An example
of that is $C_n$, the cycle on $n$ vertices. It is easy to see
that the broadcast time of any spanning tree of $C_n$ is $P_n$ the
path on $n$ vertices and $b(P_n) = n - 1 = 2b(C_n) - 1$ when $n$
is even.

%Given the minimum broadcast time of a graph, $t_{min}$, one can conclude
%an upper bound on the diameter ,$d$, of the graph, $d \leq 2t_{min}+2$. This
%is so because there cannot be any vertex in the graph that is at a distance
%more than $t_{min}$ from a broadcast center. Moreover, the broadcast center of a
%graph can have a star shape, no two vertices in the broadcast center are
%at a distance more than $2$ from each other. Now we
\chapter{Future Work}
In the previous chapter we presented the already completed part of
our research. In this chapter we present further research problems that
we plan to tackle.

\section {Graphs With More Than One Cycle}
One extension of the trees is the graph where $n$ cycles are connected
by $n-1$ edges. In other words this graph has a tree like structure 
where the nodes are substituted by cycles.
Since the broadcast problem is solved in trees and unicyclic graphs 
the next step is to consider graphs with more than one cycle and the 
simplest kind of graphs with cycles is the one where the structure 
connecting the cycles is a tree.
We will design a polynomial (very likely linear) algorithm to calculate the 
broadcast time of such graphs. The approach will be a bottom up strategy
where the broadcast time of the leaf cycles will be calculated. 
The problem boils down to repeatedly solving problems of this kind: 
Given a cycle of size $k$ where different vertices have an extra edge connecting them 
to another graph but with a known broadcast time and scheme. We 
will develope an $O(k)$ algorithm to calculate the broadcast time of the cycle. 

Next, we will generalize the definition of "graphs with more than one cycles" 
and will consider the so called Cactus graphs. Cactus graphs are graphs 
where no two cycles have more than a 
vertex in common. This is a graph where another degree of 
complexity is introduced since the cycles might have a vertex in common while 
in the previous case we had at least one edge between any two cycles. 
The following definition can give a better insight, a graph is a 
cactus if every edge is part of at most one cycle. 
They can be constructed from trees by replacing every edge by a 
cycle of arbitrary size. From the preceeding definition
we can see that the cycles have at most one vertex in common.
We will study the broadcasting problem in cactus graphs. We 
will develope a polynomial algorithm to calculate the broadcast 
time of a any vertex in a cactus graph. 

\section{Construction of optimal unicyclic graphs}
\label{sec:nmProblem}
As we explained in the literature review (chapter \ref{ch:LitRev}) there are two main
problems that has been studied quite extensively. One was finding the broadcast time given
a graph $G$, the second was given a number $n$ construct a garph $G$ on $n$ vertices and minimum
possible number of edges such that the broadcast time of the graph is the theoretical minimum i.e. 
$\lceil log n \rceil$. We also mentioned a third problem which we called the $(n,m)$ problem. Here 
we develope more on this problem. Formally speaking, the $(n,m)$ problem is to find the least 
broadcast time of all graphs on $n$ vertices and $m$ edges and to construct such a graph.
To the best of our knowledge this problem has been solved only for the case of trees, i.e.
$(n,n-1)$. Khatchatrian and Harutyunyan \cite{Kh90}  and Labahn \cite{RL89} independently solved this problem in
the classical broadcast model. The same problem was treated in the $k-broadcasting$ model by 
Harutyunyan and Liestman in \cite{HL01}. The latter model differs from the classical model 
only in the fact that a given vertex $v$ can inform up to $k$ of its neighbours in parallel 
in one time unit.

The strategy to solve the $(n,m)$ problem for trees has been to solve the "inverse problem" first,
from which the solution of the $(n,m)$ is obtained. The "inverse problem" is defined as follows:
given a diameter $d$ and a broadcast time $t$, what is the maximum number of vertices, $w(t,d)$, that a tree
can have such that broadcasting can be finished within $t$ time units and where the diameter of the
tree is equal to $d$. After answering this question on can get the solution of the original problem
by finding $min\{ t\in \mathbb{N} | max_{d \leq t} w(t,d) \geq n\}$.

 
\section{Graphs with Bounded Treewidth}
Many problems that are NP complete in general graphs have polynomial
solutions when restricted to graphs with bounded treewidth \cite{ALS91}. These include
vertex cover, chromatic number, clique, independent set, and Hamiltonian cycle problems.
This motivates us to study the broadcasting problem on graphs with
bounded treewidth. Before we proceed any further, we will introduce
the ideas of graphs decomposition, tree decomposition and treewidth.
In \cite{Schind00} it is proved that broadcasting and even more general version of this problem 
becomes easy for graphs with good decomposition properties. 


\subsection{Tree Decomposition and Treewidth}
In this section we will introduce the idea of tree decomposition of a graph $G$ \cite{Bod93}. This will lead to 
the definition of a quantity called the treewidth. 
A tree decomposition of a graph $G = (V,E)$ is the pair $(X, T)$ where $X = \{X_i | i \in I, X_i \subset V \}$ 
($I$ is the set of integers)
and $T$ is a tree whose vertices are the subsets $X_i$. The decomposition satisfies the following
conditions:
\begin{enumerate}
\item $\cup_{i \in I} X_i = V$ 
\item For all edges $(u,v)$ there exists an $i$ such that $u,v \in X_i$. 
\item Let $X_j$ be on the unique path from $X_i$ to $X_k$ in $T$, then $X_i \cap X_j \subseteq X_j$.
\end{enumerate}
The width of a tree decomposition is defined to be the maximum size of subsets $X_i$ minus 1, i.e.
$max_{i\in I} |X_i| - 1$. The treewidth of a graph $G$, $tw(G)$, is defined to be the minimum width of all the 
possible tree decompositions of $G$. A tree decomposition with the minimum treewidth is called an optimal
tree decomposition. Unfortunately, computing the treewidth of a general graph $G$ is NP complete \cite{ACP87}.
The treewidth is a measure which shows how close is the graph to being a tree. It is defined in a 
way that the treewidth of a tree is 1. In the following 2 subsections, we introduce graph families 
which have a bounded treewidth.

\subsection{Almost trees}
Before we present anything, we need to introduce some graph theoretic terms that will 
be needed to define the different graphs. 
A connected graph is a graph where there is a path connecting any two vertices $u$ and $v$.
A connected component is a maximal connected subgraph of a graph $G$. The vertex cut
of a graph $G$ is the set of vetices whose removal (together with the incident edges) makes
the graph $G$ disconnected. The connectivity of a graph $G$, denoted as $\kappa(G)$ is 
the size of the smallest vertex cut of $G$. A biconnected graph $G$ has $\kappa(G) = 2$, in other
words there are two vertices whose removal makes $G$ disconnected.  %(Menger's theorem)
A graph is an almost tree ($k$) if every biconnected component has the 
property that there are at most $k$ edges not in a spanning tree of this biconnected component.
We will study the broadcasting algorithm in this family of graphs. More specifically, we will
consider graphs in the different subfamilies where $k$ is a given constant such as 2, 3 and 
higher. Note that the case $k=1$ degenerates to the cactus graphs which we introduced above.

\subsection{k-trees and Partial k-trees}
A k-tree is defined recursively as follows \cite{Bod93}:
\begin {enumerate}
\item A complete graph on $k$ vertices is a k-tree.
\item A k-tree on $n+1$ vertices can be obtained from a k-tree
on $n$ vertices by adding a vertex adjacent to $k$ vertices (which will
naturally be a k-clique).
\end{enumerate} 
A partial k-tree is defined to be any subgraph of a $k-tree$. In other words, a partial
$k-tree$ has can be obtained from a $k-tree$ by keeping all the vertices and taking a subset
of the edges. 
In the literature the partial 2-trees have been studied often under the name of 
Series-Parallel trees, SP-tree. 
A partial k-tree is a subgraph of a k-tree. The notion of a partial k-tree is intimately
related to the notion of treewidth. Specifcally, a graph has treewidth k precisely if
it is a partial k-tree. A k-tree is a maximal graph with treewidth $k$.

Partial k-trees are graphs where the treewidth is bounded by $k$.
We will consider these graphs for broadcasting problem and will try to get either
exact broadcast schemes or most probably approximation algorithms. Again 
we will consider the subfamilies with small constant values of $k$ such as 2, 3 and above.

%\section{Odd Graphs}

%\section{Graphs with weighted vertices}

%\section {fat trees and k-ary n-trees}
%Probably not useful to us. 


\chapter {Work Plan and Conclusion}
In this chapter we summerize the main problems that were suggested in this proposal. 
Trees have been the only type of non-trivial graphs that has been found to have a polynomial solution
to the broadcast problem. The problem is in general NP complete so there is no hope of
finding a solution to the general problem. Instead, we focus on particular families of
graphs and try to give a polynomial solutions if possible otherwise approximation algorithms
will be presented. 
Adding the simplest kind of complication the trees is to add another edge. This gives rise to the
family of unicyclic graphs. We studied broadcasting in unicyclic graphs and presented a linear algorithm.
The next step that we adopted is to study graphs with multiple cycles. Hence, the tree with cycles as nodes and
cactus graphs were considered. In these families we expect to obtain polynomial solutions to the problem.

Next we consider graphs with good decomposition properties. We consider tree decompositions of graphs
and introduce the notion of treewidth. Our goal is to study graphs with bounded treewidths in order to
get approximation algorithms. Finally we consider the family of graphs which are considered to be a 
generalization of cactus graphs. These graphs are called almost trees with parameter $k$. These are
graphs where every biconnected component has at most $k$ edges not in a spanning tree of the component. 
We will consider different subclasses of this family where $k$ is an integer 2, 3 and above and will
try to find broadcast algorithms if possible or approximation algorithms or heuristics. 

Last but not least, we will consider the problem of finding the minimum broadcast time that
a unicyclic graph on $n$ vertices can have. This is a special case of the so called $(n,m)$ problem,
which is the problem to find the least broadcast time among all graphs on $n$ vertices and $m$ edges. 

The time plan for this work is 2 years. In \ref{fig:timeSchedule} we detail
the major milestons for this phd program and give a rough estimate of the 
sequence and duration of the remaing problems. 
\begin{figure}
\center
%  \vspace {0pt}
  % Requires \usepackage{graphicx}
  \includegraphics[scale = 1]{timeSheet.eps}\\
  \caption{ Time Schedule }
  \label{fig:timeSchedule}
%  \vspace {+10pt}
\end{figure}


%=============================================================================
%\bibliography{mybib}

%\begin{thebibliography}{10} \setlength {\itemsep } {-2mm}
\begin{footnotesize}
\begin{thebibliography}{10}


\bibitem{AC01}
W. Aiello, F. Chung, L. Lu, Random evolution in massive graphs,
\textit{Proceedings of the 42nd Annual IEEE Symposium on
Foundations of Computer Science, FOCS'01}, 2001, pp. 510-519.

\bibitem{ALS91}
S. Arnborg, J. Lagergren, D. Seese, Easy Problems for Tree-Decomposable Graphs,
Journal of Algorithms, 12, pp 308 - 340 (1991).

\bibitem{ACP87}
S. Arnborg, D.G. Corneil, A. Proskurowski, Complexity of finding embeddings in a k-tree,
SIAM J. Alg. Disc. Meth. 8 (1987), 277–284

\bibitem{Ba98}  % new added.
A. Bar-Noy, S. Guha, J. Naor and B. Schieber. Multicasting in
Heterogeneous Networks, \textit{Proc. of ACM Symp. on Theory of
Computing, STOC'98}, 1998.

\bibitem{RBJS}
R. Beier, J. F. Sibeyn, A powerful heuristic for telephone
gossiping, \textit{Proc. of the 7th International Colloquium on
Structural Information \& Communication Complexity, SIROCCO'00},
L'Aquila, Italy, 2000, pp. 17-36.

\bibitem{BP88}
J-C Bermond and C. Peyrat, Broadcasting in deBruijn Networks, \textit{
Proc. $19^th$ Southeastern Conference on Combinatorics}, Graph Theory
and Computing, Congressus Numerantium, 66:283-292, 1988.

\bibitem{Be95}
J. -C. Bermond, P. Fraigniaud, J. Peters, Antepenultimate
broadcasting, \textit{Networks}. 26 (1995), pp. 125-137.

%\bibitem{Be97}
%J. -C. Bermond, H. A. Harutyunyan, A. L. Liestman, and S. Perennes.
%A note on the dimensionality of modified Kn\"{o}del graphs,
%\textit{Int. J. Found. Comp. Sci.} 8 (1997), pp. 109-117.

\bibitem{Be92}
J. -C. Bermond, P. Hell, A. L. Liestman, J. G. Peters, Sparse
broadcast graphs, \textit{Discrete Appl. Math.} 36 (1992), pp.
97-130.

%\bibitem{HLP92}
%J. -C. Bermond, P. Hell, A. L. Liestman, and J. G. Peters,
%Broadcasting i n bounded degree graphs. \textit{SIAM J. Discr.
%Math.} 5: 10-24, 1992.

\bibitem {Bod93}
H.L. Bodlaender, A tourist guide through treewidth, Acta Cybernet. 11 (1993) pp.1-21.

\bibitem{MD94}
M. J. Dinneen. The complexity of broadcasting in bounded-degree networks,
Tech. Report LACES-05C94 -31, Los Alamos National Laboratory, 1994

\bibitem{Di99}
M. J. Dinneen, J. A. Ventura, M. C. Wilson, G. Zakeri, Compound
constructions of broadcast networks, \textit{Discrete Math.} 93
(1999), pp. 205-232.

\bibitem{DFF}
M. J. Dinneen, M. R. Fellows, V. Faber, Algebraic constructions of
efficient broadcast networks, in: {\em Applied Algebra, Algebraic
Algorithms and Error- Correcting Codes} 9, Lecture Notes in
Computer Science, vol. 539, Springer, Berlin, 1991, pp. 152-158.

\bibitem{MD96}
M. B. Doar, A better model for generating test networks, in: IEEE
GLOBECOM'96, London, UK, 1996.

\bibitem{El02}  % new added.
M. Elkin, G. Kortsarz. A combinatorial logarithmic approximation
algorithm for the directed telephone broadcast problem,
\textit{Proc. of ACM Symp. on Theory of Computing, STOC'02}, 2002,
pp. 438-447.

\bibitem{EK03}
M. Elkin and G. Kortsarz, Sublogarithmic approximation for
telephone multicast: path out of jungle, \textit{Proc. of
Symposium on Discrete Algorithms, SODA'03}, Baltimore, Maryland,
2003, pp. 76-85.

\bibitem{Fa79N} A. M. Farley, Minimal broadcast networks,
\textit{Networks} 9 (1979) 313 - 332.

%\bibitem{AF78} A. Farley and S. Hedetniemi, Broadcasting in grid
%graphs. in: Proc. Ninth SE Conf. on Combinatorics, Graph Theory and
%Computing, Utilitas Mathematica, Winnipeg, 1978, pp. 275-288.

\bibitem{Fa79D}
A. M. Farley, S. T. Hedetniemi, A. Proskurowski, S. Mitchell,
Minimum broadcast graphs, \textit{Discrete Math.} 25(1979), pp.
189-193.

\bibitem{UF90}
 U. Feige, David Peleg, P. Raghavan and E. Upfal, Randomized
broadcast in networks, \textit{Proc. of International Symposium on
Algorithms, SIGAL'90}, 1990, pp. 128-137.

\bibitem{PF94}
P. Fraigniaud, E. Lazard, Methods and problems of communication in
usual networks, Discrete Appl. Math. 53 (1994) 79-133.

\bibitem{FP97}
P. Fraigniaud, S. Vial, Approximation algorithms for broadcasting
and gossiping, J. Parallel and Distrib. Comput. 43(1) (1997)
47-55.

\bibitem{FPSV}
P. Fraigniaud, S. Vial, Heuristic Algorithms for Personalized
Communication Problems in Point-to-Point Networks, \textit{Proc.
of the 4th Colloquium on Structural Information and Communication
Complexity, SIROCCO'97}, 1997, pp. 240-252.

\bibitem{FP99}
P. Fraigniaud, S. Vial, Comparison of Heuristics for One-to-All
and All-to-All Communication in Partial Meshes, \textit{Parallel
Processing Letters}, 9(1), 1999, pp. 9-20.

%\bibitem{Ga89}
%L. Gargano, U. Vaccaro, On the construction of minimal broadcast
%networks, \textit{Networks} 19, 1989, pp. 673 - 689.

\bibitem{GP91}
M. Grigni, D. Peleg, Tight bounds on minimum broadcast networks,
\textit{SIAM J. Discr. Math.} 4 (1991), pp.207–222.

\bibitem{H07}
H. A. Harutyunyan, An efficient vertex addition method for
broadcast networks, \textit{Internet Mathematics} 2007, to appear.

\bibitem{HX07}
H. A. Harutyunyan and X. Xu. New Construction of Broadcast Graphs, 
\textit{11th International Conference Information Visualization}, 2007, 
pp. 751 - 756.

\bibitem{Ha99}
H. A. Harutyunyan, A. L. Liestman, More broadcast graphs.
\textit{Discr. Appl. Math.} 98, (1999), pp. 81-102.

\bibitem{HL01}
H. A. Harutyunyan, A. L. Liestman, k-Broadcasting in Trees.
\textit{Networks} 38(3), 2001, pp. 163-168.


\bibitem{HL03}
H. A. Harutyunyan, A. L. Liestman, On the monotonicity of the
broadcast function, \textit{Discr. Math.} 262, (2003), pp.
149–157.

\bibitem{HM07}
H. A. Harutyunyan, E. Maraachlian, Linear Algorithm for
Broadcasting in Unicyclic Graphs, \textit{Proc. 13th Annual COCOON
2007}, LNCS 4598 (2007), pp. 372–383.

\bibitem{HS05}
H. A. Harutyunyan, B. Shao, An Efficient Heuristic for
Broadcasting in Networks, \textit{Journal of Parallel and
Distributed Computing} 66(1), 2006, pp. 68-76.

\bibitem{HS07}
H. A. Harutyunyan, B. Shao, Efficient Heuristics for
Message Dissemination in Networks, \textit{Proceedings of the
25th IASTED International Mulit-conference Parallel and
Distributed Computing and Networks}, 2007, pp. 196-202.

\bibitem{HHL88}
S.M Hedetniemi, S.T. Hedetniemi, A.L. Liestman, A survey of
gossiping and broadcasting in communication networks, Networks, 18
(1988) 319-349.

\bibitem{HJM93}
J. Hromkovic, C.-D Jeschke, and B. Monien, Optimal algorithms for
dissemination of information in some interconnection networks, 
Algorithmatica, 10(1): 24-40, 1993

\bibitem{HKMP96}
J. Hromkovic, R. Klasing, B. Monien, R. Peine, Dissemination of
information in interconnection networks, in: Combinatorial Network
Theory, D.-Z. Du, D.F.Hsu(eds.), Kluwer Academic Publishers, 1996,
pp. 125-212.

\bibitem{Jo79}
D. Johnson and M. Garey, Computers and Intractability: A Guide to
the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979)

\bibitem{Kh90} L. Khachatrian and H. Harutyunyan, Construction of
new classes of minimal broadcast networks, in: \textit{Proceedings
3rd International Colloquium on Coding Theory, Dilijan, Armenia},
1990, pp. 69-77.

\bibitem{KMPS94}
R. Klasing, B. Monien, R. Peine, E. A. St\"{o}hr, Broadcasting in
butterfly and deBruijn networks, Discrete Appl. Math. 53 (1994)
183-197.

\bibitem{JRS98}
A. Jakoby, R. Reischuk, C. Schindelhauer, The Complexity of Broadcasting
in Planar and Decomposable Graphs, Discrete Applied Mathematics,
Vol. 83, 1998, 179-206.

\bibitem{KP95}
G. Kortsarz and D. Peleg, Approximation algorithms for minimum
time broadcast, in: SIAM J. Discrete Math. 8 (1995) 401-427.

\bibitem{RL89}
Roger Labahn, Extremal broadcasting problems, 
Discrete Appl. Math. 23 (1989) 139-155.

\bibitem{LP88}
A. Liestman and J.Peters, Broadcast networks of bounded degree, 
\textit{SIAM, J. Disc. Math}, vol. 1, pp 531 - 540, 1988.

\bibitem{LT92}
T. Leighton, Introduction to Parallel Algorithms and Architectures:
Array-Trees-Hypercubes, Morgan-Kaufmann Publishers, San Mateo,
California, 1992.


\bibitem{MM93}
M. Middendorf, Minimum broadcast time is NP-complete for 3-regular 
planar graphs and deadline 2, Information Processing Letters, 46(6): 281-287,
1993.

\bibitem{RR94}
R. Ravi, Rapid Rumor Ramification: Approximating the minimum
broadcast time, \textit{Proc. of 35th Symposium on Foundation of
Computer Science, FOCS'94}, 1994, pp. 202-213.

\bibitem{SCH81}
P. J. Slater, E. J. Cockayne, S. T. Hedetniemi, Information
dissemination in trees, SIAM J.Comput. 10(4) (1981) 692-701.

\bibitem{GW84}
P. Scheuerman, G. Wu, Heuristic Algorithms for Broadcasting in
Point-to-Point Computer Network, IEEE Transactions on Computers
C-33(9) (1984) 804-811.

\bibitem{Schind00}
Christian Schindelhauer, On the Inapproximability of Broadcasting Time,
Proc. of the 3rd International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX'00), 2000, 226-237

\bibitem{ZC96}
E. W. Zegura, K. Calvert, S. Bhattacharjee, How to model an
internetwork, \textit{Proc. The IEEE Conf. on Computer
Communications, INFOCOM'96}, San Francisco, CA, 1996.

\end{thebibliography}


%\bibliographystyle{plain}
%\bibliography{string,itu,rfc,i-d}
\end{footnotesize}

\end{document}
