% The Chicago Journal of Theoretical Computer Science, Volume 1996, Article 3
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1996 by Massachusetts Institute of Technology
%
\newtoks\rstyle
\rstyle={cjlook}
%
\ifx\documentclass\undeftex
\documentstyle[v1.1,published]{cjstruct}
\else
\documentclass[v1.1,published]{cjstruct}
\fi
%
% Local style resources for this article.
%
\usestyleresource{amstex}
\usestyleresource{thrm}
\usestyleresource{epic}
\usestyleresource{eepic}
\usestyleresource{transfig}

% Local macro definitions for this article.
%
\catcode`\@=11
\ifx\nopagebreakbeginpar\undeftex
  \newcommand{\nopagebreakbeginpar}{\@beginparpenalty10000}
\fi
\catcode`\@=12
%
\newcommand{\pathsingraph}{\mathcal{P}}
\newcommand{\edgemap}[1]{\mathcal{#1}}
\newcommand{\funcspace}[2]{#1\mathbin{\rightarrow}#2}
\newcommand{\oftype}{\colon}
\newcommand{\loadonnode}{\mathcal{L}}
\newcommand{\setsize}[1]{\left|#1\right|}
\newcommand{\setof}[2]{\left\{\,#1\mid#2\,\right\}}
\newcommand{\powerset}[1]{\mathcal{P}(#1)}
\newcommand{\universe}[1]{\Bbb{#1}}
\newcommand{\hopcount}{\mathcal{H}}
\newcommand{\textsupscript}[2]{\(\text{#1}^{\text{#2}}\)}
\newcommand{\virtchan}{\mathit{VC}}
\newcommand{\virtpath}{\mathit{VP}}
\newcommand{\vectnorm}[2]{\|#1\|_{#2}}
\newcommand{\subvector}[3]{#1[#2\colon #3]}
\newcommand{\constvect}[2]{\subvector{\vec{#1}}{1}{#2}}
\newcommand{\vectcat}{\bullet}
\newcommand{\vecpairseq}[1]{\mathcal{#1}}
\newcommand{\subvecinc}[2]{#1^{\text{trans}(#2)}}
\newcommand{\leftseq}[1]{#1_{L}}
\newcommand{\rightseq}[1]{#1_{R}}
\newcommand{\sumvecseq}{\Sigma}
\newcommand{\mathlabel}[1]{\text{#1}}
\newcommand{\transformsto}{\rightarrow}
\newcommand{\maxhopcount}{\hbar}
\newcommand{\mult}{\cdot}
\newcommand{\orderof}[1]{O(#1)}
\newcommand{\neighborhood}{\mathcal{N}}
\newcommand{\radius}{\mathit{Rad}}
\newcommand{\setofclust}[1]{\mathcal{#1}}
\newcommand{\logicand}{\wedge}
\newcommand{\unionset}{\bigcup}
\newcommand{\extender}{\varepsilon}
\newcommand{\limiter}{\lambda}
\newcommand{\combchoice}[2]{\binom{#1}{#2}}
%
\renewenvironment{algorithm}[2]{%
  \begingroup
  \proglang={#1}
  \begin{enumerate}
  \setlength{\itemsep}{0ex}
  \setlength{\parsep}{0ex}
%
}{%
  \end{enumerate}
  \endgroup
}
\renewcommand{\kwd}[1]{\textbf{#1}}
\renewcommand{\comment}[1]{(#1)}
\mathstyleclass{\prog}{\mathord}{\textit}
\mathstyleclass{\progfunc}{\mathord}{\textit}
\mathstyleclass{\progstat}{\mathord}{\textsc}
\mathstyleclass{\progconst}{\mathord}{\textit}
\newcommand{\proglab}[1]{\textit{#1}}
\newcommand{\assigned}{\mathrel{\leftarrow}}
\newcommand{\progind}{\quad}
%
\newcommand{\problemlabel}[1]{\textmd{\textsc{#1}}}
%
% Custom visual formatting.
%
\newcommand{\prooffontshape}{\fontshape{n}\selectfont}
\newcommand{\exampfontshape}{\fontshape{n}\selectfont}
\newlength{\customlabelskip}
\setlength{\customlabelskip}{3ex}
\newlength{\customarraycolsep}
\setlength{\customarraycolsep}{0.25em}
\newcommand{\customdotgapa}{100}
\newcommand{\customdotgapb}{100}
\newcommand{\complsupscrstrut}{\rule{0ex}{2.5ex}}
\newcommand\nohyphenl[1]{{\discretionary{}{}{}{#1}}}
\newcommand\nohyphenr[1]{{{#1}\discretionary{}{}{}}}
%
% Macros for the publisher's comment
%
% The circle R symbol for a registered trade name is adapted from the
% circled c copyright symbol defined in The TeXBook by Donald Knuth.
%
\def\registered{\({}^{\ooalign%
    {\hfil\raise.07ex\hbox{{\tiny\textup{R}}}%
    \hfil\crcr\scriptsize\mathhexbox20D}}\)}
%
% Macros for the editors' comment
%
% The cross symbol indicates a recently deceased editor.
%
\ifx\deceased\undeftex
  \newcommand{\deceased}[1]{\dag#1}
\fi
%
% end of local macro definitions for this article
%
\begin{document}
%
\begin{articleinfo}
%
\publisher{The MIT Press}
%
\publishercomment{%
  {\Large
    \begin{center}
      Volume 1996, Article 3\\
      \textit{31 October 1996}
    \end{center}
  }
  \par\noindent
  ISSN 1073--0486\@. MIT Press Journals, 55 Hayward St., Cambridge, MA
  02142 USA; (617)253-2889;
  \emph{journals-orders@mit.edu, journals-info@mit.edu}\@.
  Published one article at a time in \LaTeX\ source form on the
  Internet\@. Pagination varies from copy to copy\@. For more
  information and other articles see:
  \begin{itemize}
    \item \emph{http://www-mitpress.mit.edu/jrnls-catalog/chicago.html}
    \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/}
    \item \emph{gopher.mit.edu}
    \item \emph{gopher.cs.uchicago.edu}
    \item anonymous \emph{ftp} at \emph{mitpress.mit.edu}
    \item anonymous \emph{ftp} at \emph{cs.uchicago.edu}
  \end{itemize}
  \sentence
  \par\noindent
  The \emph{Chicago Journal of Theoretical Computer Science} is
  abstracted or indexed in \emph{Research Alert,\registered
  SciSearch,\registered Current Contents\registered/Engineering
  Computing \& Technology}, and \emph{CompuMath Citation Index\@.\registered}
}
%
\copyrightstmt{%
  \copyright 1996 The Massachusetts Institute of Technology\@.
  Subscribers are licensed to use journal articles in a variety of
  ways, limited only as required to insure fair attribution to authors
  and the journal, and to prohibit use in a competing commercial
  product\@. See the journal's World Wide Web site for further
  details\@. Address inquiries to the Subsidiary Rights Manager, MIT
  Press Journals; (617)253-2864;
  \emph{journals-rights@mit.edu}\@.\pagebreak[2]
}
%
\journal{Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science}
%
\journalcomment{%
  The \emph{Chicago Journal of Theoretical Computer Science}
  is a peer-reviewed scholarly
  journal in theoretical computer science\@. The journal is committed
  to providing a forum for significant results on theoretical
  aspects of all topics in computer science\@.
  \par
  \begin{trivlist}
    \item[\emph{Editor in chief:}] Janos Simon
    \item[\emph{Consulting editors:}]
      Joseph Halpern, Stuart A.\ Kurtz, Raimund Seidel
    \item[\emph{Editors:}]
      \begin{tabular}[t]{lll}
        Martin Abadi & Greg Frederickson & John Mitchell \\
        Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\
        Eric Allender & Georg Gottlob & Gil Neiger \\
        Tetsuo Asano & Vassos Hadzilacos & David Peleg \\
        Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\
        Eric Bach & Maurice Herlihy & James Royer \\
        Stephen Brookes & Stephen Homer & Alan Selman \\
        Jin-Yi Cai & Neil Immerman & Nir Shavit \\
        Anne Condon & \deceased{Paris Kanellakis} & Eva Tardos \\
        Cynthia Dwork & Howard Karloff & Sam Toueg \\ 
        David Eppstein & Philip Klein & Moshe Vardi \\
        Ronald Fagin & Phokion Kolaitis & Jennifer Welch \\
        Lance Fortnow & Stephen Mahaney & Pierre Wolper \\
        Steven Fortune & Michael Merritt
      \end{tabular}
    \vspace{1ex}
    \item[\emph{Managing editor:}] Michael J.\ O'Donnell
    \vspace{1ex}
    \item[\emph{Electronic mail:}] \emph{chicago-journal@cs.uchicago.edu}
  \end{trivlist}
\sentence
\pagebreak[0]
}
%
\bannerfile{cjtcs-banner.tex}
%
\volume{1996}
%
\articleid{3}
%
\selfcitation{
     @article{cj96-03,
       author={Ornan Gerstel and Israel Cidon and Shmuel Zaks},
       title={Optimal Virtual Path Layout in {ATM} Networks with Shared
         Routing Table Switches},
       journal={Chicago Journal of Theoretical Computer Science},
       volume={1996},
       number={3},
       publisher={MIT Press},
       month={October},
       year={1996}
     }
}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\title{Optimal Virtual Path Layout in ATM Networks with Shared Routing
  Table Switches}
\shorttitle{Optimal Virtual Path Layout in ATM}
\collectiontitle{Selected Papers from PODC 1994}
\editorname{David Peleg}
%
\editorcomment{%
This article is included in the special issue, \emph{Selected Papers 
from PODC 1994}, containing articles based on extended abstracts presented at
the \emph{13th Annual ACM Symposium on Principles of Distrituted Computing},
Los Angeles, California, August 1994\@. This special issue was edited by 
David Peleg\@.
}
%
\begin{authorinfo}
%
% Correction to error in cjstruct.sty version 1.1.
%
\def\fixversion{1.1}
\ifx\cjversion\fixversion
  \renewcommand{\printname}[1]{
    \global\authorstring={#1}
    \global\authorstrue
    \ifinfo\item Printed name: #1\fi
  }
\fi
%
% End of correction.
%
   \printname{Ornan Gerstel}
   \collname{}{Gerstel, Ornan}
   \begin{institutioninfo}
       \instname{IBM}
       \department{Thomas J.\ Watson Research Center}
       \address{}{Hawthorne}{NY}{USA}{10532}
   \end{institutioninfo}
   \email{ori@watson.ibm.com}
\end{authorinfo}
%
\begin{authorinfo}
   \printname{Israel Cidon}
   \collname{}{Cidon, Israel}
   \begin{institutioninfo}
       \instname{Technion}
       \department{Electrical Engineering Department}
       \address{}{Haifa}{}{Israel}{3200}
   \end{institutioninfo}
   \email{cidon@ee.technion.ac.il}
\end{authorinfo}
%
\begin{authorinfo}
   \printname{Shmuel Zaks}
   \collname{}{Zaks, Shmuel}
   \begin{institutioninfo}
       \instname{Technion}
       \department{Computer Science Department}
       \address{}{Haifa}{}{Israel}{3200}
   \end{institutioninfo}
   \email{zaks@cs.technion.ac.il}
\end{authorinfo}
%
\shortauthors{Gerstel, Cidon, Zaks}
%
\support{
  Part of Ornan Gerstel's work was done while he was with the Computer
  Science Department, Technion, Haifa 32000, Israel. Part of Israel
  Cidon's work was done while he was with Sun Microsystems Labs, 2550
  Garcia Avenue, Mountain View, CA 94043.
}
%
\begin{editinfo}
  \submitted{16}{11}{1994}\reported{15}{12}{1994}
  \submitted{10}{3}{1995}\reported{16}{11}{1995}
  \submitted{4}{6}{1996}\reported{30}{7}{1996}\published{31}{10}{1996}
\end{editinfo}
\end{articleinfo}
%
\begin{articletext}
%
\begin{abstract}
%
\apar{Abstract-1}
In this paper we present a new model for routing that occurs in
high-speed ATM networks\@. Within this model we define a general
routing problem, called a virtual path layout\@. Given a network of
nodes (switches) and links, one must find a set of paths in the
network, termed the virtual path layout, whereby each pair of nodes
may connect using a route that is a concatenation of a small number of
virtual paths and is also short in terms of the network links it
traverses\@. Each such layout implies a utilization of the routing
tables in the network's nodes\@. Our goal is to find a layout that
minimizes this utilization, assuming that each such node has a central
routing table\@. We prove that this problem is NP-complete, and
consequently focus on a simpler problem, in which it is required to
connect all nodes to a single switch\@. Next, we prove that even this
problem is NP-complete, and restrict some of the assumptions to yield
a practical subproblem, for which we present a polynomial-time greedy
algorithm that produces an optimal solution\@. Finally, we use this
restricted problem as a building block in finding a suboptimal
solution to the original problem\@. The results exhibit a tradeoff
between the performance of a routing scheme and its resource
utilization\@.
%
\end{abstract}
%
This article contains results that were presented at the \emph{13th
Annual ACM Symposium on Principles of Distributed
Computing}~\cite{cj96-04-15}\@.
%
{\ifx\customadjusta\undeftex\else\customadjusta\fi
\asection{1}{Introduction}
%
\ifx\customadjustb\undeftex\else\customadjustb\fi
\asubsection{1.1}{Background}
%
\ifx\customadjustc\undeftex\else\customadjustc\fi
\apar{1.1-1}
The advent of fiber optic media has dramatically changed classical
views on the role and structure of digital communication networks\@.
Specifically, the sharp distinction (in terms of node hardware
architectures, network management techniques, routing schemes, and
various theoretical aspects) between telephone networks, cable
television networks, and computer networks, has been replaced by a
unified approach\@. In this integrated approach (termed B-ISDN),
real-time, high-quality video and audio, and very large amounts of
data are integrated into a single digital network that will support
numerous applications---ranging from interactive television, video
conferencing systems, and video-phone to distributed virtual reality
systems\@.
%
\apar{1.1-2}
While fiber optic cables are capable of transferring very large
amounts of data (around \(10^{10}\) bits per second), the nodes that
connect these cables cannot accommodate this flood of data in
software\@. For this reason, the routing of data packets, which is
traditionally done by the network layer software, has been moved to
special-purpose very fast hardware, a fact that requires very simple
routing algorithms\@.
%
\apar{1.1-3}
The most common solution for this new network architecture is called
\emph{Asynchronous Transfer Mode} (ATM for short), and is thoroughly
described in the literature \cite{cj96-04-04,cj96-04-16,cj96-04-21,cj96-04-08}
\footnote{ A different approach to fast routing is based on automatic
network routing (ANR) and was implemented in PARIS and plaNET
\cite{cj96-04-07,cj96-04-05,cj96-04-06}\@.}\@. ATM is based on relatively small
fixed-size packets called \emph{cells}\@. Each cell is routed
independently, based on two small routing fields at the cell header,
called the \emph{virtual channel index} (VCI) and the \emph{virtual
path index} (VPI)\@.
%
\apar{1.1-4}
At each intermediate node, these fields serve as indices to two
routing tables (the VCI serves as an index to one table, and the VPI
to the other), and the routing is done in accordance with
predetermined information from the appropriate entries (which is
entered into the tables during the setup of connections in the
network)\@.
%
\apar{1.1-5}
Routing in ATM is hierarchical in the sense that the VCI of a cell is
ignored as long as its VPI is not null\@. This algorithm effectively
creates two types of predetermined simple routes in the network:
routes that are based on VPIs (called \emph{virtual paths} or VPs),
and routes that are based on VCIs (called \emph{virtual channels} or
VCs)\@. The latter may be viewed as a concatenation of complete~VPs\@.
%
\apar{1.1-6}
}
VPs and VCs have different roles in the network\@. While VCs are used
for creating connections between two users of the network that wish to
communicate (e.g., a telephone call), VPs have an internal network
role (decreasing the overhead caused by network management
activities), and are used for bundling several VCs that share part of
their route\@.
%
\apar{1.1-7}
The VC and VP concepts have been extensively discussed in the
communications literature; however, to the best of our knowledge, the
problem of how VPs should be laid out in a given communication network
has never been addressed analytically\@. A few heuristics have been
proposed and experimented \cite{cj96-04-03,cj96-04-17}\@. This problem is of
practical importance, since the layout of VPs in a network determines
many of the network's important performance characteristics, such as
the overhead and delay of the setup of a new VC, the load on the VP
routing tables, and various fault-tolerance qualities\@.
%
\asubsection{1.2}{Our Work}
%
\apar{1.2-1}
All of the above calls for a new model---different from the classical
model for routing in computer networks---for both describing the network
and measuring the performance of algorithms on it\@. In Section~2 we
define a model for routing in ATM networks, and determine the essential
characteristics for measuring the optimality of a given layout\@. Using
this model, we define the general layout problem for ATM\@. We then
isolate a simpler case, which can be viewed as a variant of tree routing
(analogous to the way that interval routing \cite{cj96-04-24} is used in
classical routing problems), suited for this model\@.
%
\apar{1.2-2}
In Section~3 we prove that even the simpler case is NP-complete, and
we therefore restrict ourselves to a subproblem that is general enough
for practical purposes, and present a greedy algorithm that optimally
solves the subproblem for any given tree network\@. In Section~4 we
prove the general problem to be NP-complete as well, and demonstrate
the use of the subproblem as a building block in the solution of the
general problem on arbitrary networks\@. We conclude in Section~5 by
summing up the results in the paper, and presenting open problems\@.
%
\apar{1.2-3}
We expect our contribution to be three-fold:
%
\begin{enumerate}
%
\item[1.] This paper is among the first to analytically address the
problem (together with \cite{cj96-04-13})\@. For this reason, we focus on
a relatively simple problem, with a low number of parameters\@. This is
also a first attempt to prove complexity results concerning the
problem, and to present an optimal solution for a special case (the
one-to-many layout problem on trees---see Definition~5)\@.
%
\item[2.] We believe the problem we focus on is of practical importance in
certain scenarios in ATM networks\@. In particular, our problem is most
suitable for an environment with short-lived VCs without an a priori
known bandwidth; such environments are expected to be typical for
distributed applications over ATM networks \cite{cj96-04-20}\@. Even our
restricted (polynomially solvable) problem seems to be useful for
client-server applications over~ATM\@.
%
\item[3.] We present basic techniques for deriving upper and lower bounds
on such problems (exemplified by the tree-routing problem, often used
as a benchmark case study)\@. In particular, the crux of our greedy
algorithm (i.e., the upper bound) is nonintuitive in nature, and was
formulated by the needs of its optimality proof (lower bound)\@.
%
\end{enumerate}
%
\apar{1.2-4}
The present paper is closely related to \cite{cj96-04-13}, in which a
similar model is discussed, using a different VP-table load metric (on
the edges of the graph rather than on its nodes)\@. This difference
stems from different node implementations, and seems to have an impact
on the complexity of the problem\@. In particular, we present here
NP-completeness results that we were unable to derive for the other
load metric\@.
%
\apar{1.2-5}
The simpler one-to-many problem on trees is addressed in
\cite{cj96-04-13} as well, using a different technique that is based on
dividing the tree into small subtrees and solving the problem
separately in each subtree\@. This technique yields a solution that is
asymptotically optimal under certain assumptions\@. In contrast, the
``greedy'' technique presented herein provides an optimal solution for
any given tree\@. Also, the resulting algorithm is much simpler to
implement, and has lower time complexity\@. Furthermore, while
many-to-many solutions in \cite{cj96-04-13} yield high VP-table loads,
the solution herein results in much smaller loads, by compromising the
efficient utilization of the physical network (using the concept of a
stretch factor)\@.
%
\apar{1.2-6}
A related problem is that of keeping small routing tables for routing
in conventional computer networks\@. This problem has been widely
studied
\cite{cj96-04-01,cj96-04-02,cj96-04-10,cj96-04-11,cj96-04-18,cj96-04-19,cj96-04-22}
and has yielded interesting graph decompositions and structures, but
it differs from ours in some major aspects, which deemed most of these
solutions impractical for our purposes\@. The main difference stems
from the fact that in our case there is no flexibility as to the
routing scheme itself, since this is determined by the ATM standard
\cite{cj96-04-04}\@. We therefore present a static structure in the
network, while in the conventional model, the exact routing of a
packet may be determined dynamically during the process of its routing
(as in \cite{cj96-04-02,cj96-04-01}), or by information that is based
on the name of the destination (as in~\cite{cj96-04-10,cj96-04-11})\@.
%
\apar{1.2-7}
Other differences stem from practical restrictions on the model,
in which the routing tables of each node are restricted by the same
size, while in some of the conventional solutions the total (or
average) size of the routing tables is minimized 
(e.g.,~\cite{cj96-04-10,cj96-04-11,cj96-04-22})\@.
%
\apar{1.2-8}
Our approach resembles some of the above-mentioned techniques in that
a simpler tree-routing problem is used as a building block in the
general-case solution (analogous to the way that interval routing on
trees \cite{cj96-04-24} is used in some of the routing schemes for arbitrary
graphs)\@. We use the techniques of \cite{cj96-04-02} for demonstrating the
usage of our tree-routing problem in solving the general problem\@.
%
\apar{1.2-9}
This paper is an extension of~\cite{cj96-04-15}\@.
%
\asection{2}{The Model}
%
\apar{2-1}
We first define a graph-theoretic model for our problems (for basic
terms and definitions, see \cite{cj96-04-09})\@. In our model, we have an
underlying communication network that consists of nodes and links
between nodes\@. This network is modeled by an undirected graph
\(G=(V,E)\), where \(V\) corresponds to the set of nodes and \(E\) to the
set of physical links between them\@.
%
\apar{2-2}
Due to the routing mechanism in ATM, VPs are unidirectional paths in
the network\@. However, for connection management reasons \cite{cj96-04-08},
VPs are coupled together in pairs of parallel routes in opposite
directions, effectively creating bidirectional paths\@. For simplicity,
we refer in the remainder of the paper to these bidirectional VPs
exclusively\@.
\apar{2-3}
A virtual path layout is a set of simple bidirectional paths on the 
given network, as formalized by the following definition:
%
\begin{alabsubtext}{Definition}{1}{}
%
Let \(\pathsingraph(G)\) be the set of all simple paths in
\(G\)\@. A \emph{virtual path layout} or VPL is a subset of
\(\pathsingraph(G)\)\@. Formally, it is convenient to represent a VPL
\(\Psi\) by a pair \(\Psi=(G_{\Psi},\edgemap{I})\), where
\(G_{\Psi}=(V,E_{\Psi})\) is a ``virtual'' graph and
\(\edgemap{I}\oftype\funcspace{E_{\Psi}}{\pathsingraph(G)}\) is a ``mapping''
function\@. A ``virtual'' edge \(\psi=(a,b)\in E_{\Psi}\) represents a VP
between the nodes \(a\) and \(b\)\@. The function \(\edgemap{I}(\psi)\) maps
each virtual edge \(\psi=(a,b)\) to its corresponding route in
\(G\)\@. We term this path the \emph{induced path} of~\(\psi\)\@.
%
\end{alabsubtext}
\sentence
%
For the sake of notational convenience, we refer to a path
\(p\in\pathsingraph(G)\) either as a set of edges or as a set of
nodes\@.
%
\apar{2-4}
We extend the definition of \(\edgemap{I}\) to simple paths in
\(G_{\Psi}\) as follows:
%
\begin{alabsubtext}{Definition}{2}{}
%
The induced path \(\edgemap{I}(p)\), for a path
\(p\in\pathsingraph(G_{\Psi})\),
where \(p=(\psi_{1},\psi_{2},\dots,\psi_{k})\) and \(\psi_{i}\in
E_{\Psi}\) for every \(i\), is the path obtained by concatenating the
induced paths \(\edgemap{I}(\psi_{i})\) of all~\(\psi_{i}\)s\@.
%
\end{alabsubtext}
\sentence
%
\apar{2-5}
Each VP utilizes an entry\footnote{A VP actually uses two entries in
each such routing table, for the two unidirectional VPs from which it
is composed, but we neglect this fact, as it exactly doubles the
utilization at any table\@.} in the routing table of each node that is
part of its path (be it an endpoint or an intermediate node)\@. Since
the routing tables are bounded by the ATM standard to 4,096 entries,
this resource should be carefully allocated in large networks\@. The
following load measure expresses this utilization, assuming that each
node has a central, shared routing table:\footnote{ This alternative is
applicable mainly for nodes that are based on shared memory\@. Other
node architectures are based on a separate processor for each link in
the node, which dictates a separate routing table for each link, and a
different load measure\@.}
%
\begin{alabsubtext}{Definition}{3}{}
%
The \emph{load} \(\loadonnode(v)\) on a node \(v\in V\) is the number
of VPs \(\psi\in E_{\Psi}\) that include \(v\) in their induced paths,
namely,
\(\loadonnode(v)=\setsize{\setof{\psi\in E_{\Psi}}{v\in\edgemap{I}(\psi)}}\)\@.
The load definition is extended to a VPL \(\Psi\) by
\(\loadonnode(\Psi)=\max_{v\in V}\loadonnode(v)\)\@.
%
\end{alabsubtext}
\sentence
%
\begin{alabsubtext}{Definition}{4}{}
%
Let \(\mu\in\universe{R}\) be a real number called the \emph{stretch
factor}\@. The \emph{hop count} \(\hopcount_{\mu}(v,w)\) for a pair of
nodes \(v,w\in V\) is the minimum \(k\) such that:
%
\begin{enumerate}
%
\item[1.]
\(\exists p=(\Psi_{1},\Psi_{2},\dots,\Psi_{k})\in\pathsingraph(G_{\Psi})\), 
(\(\Psi_{i}\in E_{\Psi}\) for every~\(i\)),
%
\item[2.] \(\exists x,y\in V,\psi_{1}=(v,x),\psi_{k}=(y,w)\), and
%
\item[3.] the induced path \(\edgemap{I}(p)\) is at most \(\mu\) times
longer than the shortest path between \(v\) and \(w\) in~\(G\)\@.
%
\end{enumerate}
%
If no such path exists, define \(\hopcount_{\mu}(v,w)=\infty\)
(this does not necessarily mean that \(G_{\Psi}\) is not connected)\@.
%
\end{alabsubtext}
%
\apar{2-6}
We distinguish between two problems:
%
\begin{itemize}
%
\item the general layout problem in which it is required to connect
every pair of nodes in \(V\)---we term this access pattern
``many-to-many'' (m-m for short), and
%
\item a more restricted access pattern in which it is required to
connect all nodes to a single node (called the \emph{root})---we term
this access pattern ``one-to-many''~(1-m)\@.
%
\end{itemize}
%
The VPL for m-m access is denoted by \textsupscript{VPL}{m-m}, while a
VPL for 1-m access is denoted by \textsupscript{VPL}{1-m}\@. Note that
\textsupscript{VPL}{1-m} differs from broadcasting in that the data is
not distributed from the root to all other nodes in the network, but
rather, it enables separate connections (VCs) from the root to all the
other nodes\@.
%
\apar{2-7}
The two problems are formalized by the following definition\@.
%
\begin{alabsubtext}{Definition}{5}{}
%
Let \(h>0\); \(\mu\geq 1\); let \(G=(V,E)\) be a given network; and
let \(r\in V\)\@. The following two cases correspond to the above-mentioned
problems\@.
%
\begin{itemize}
%
\item A \textsupscript{VPL}{m-m} in \(G\) is \emph{\(h\)-feasible} if
\(\max_{v,w\in V}\hopcount_{\mu}(v,w)\leq h\)\@.
%
\item A \textsupscript{VPL}{1-m} in \(G\) is \emph{\((h,r)\)-feasible}
if \(\max_{v\in V}\hopcount_{\mu}(v,r)\leq h\)\@.
%
\end{itemize}
%
\end{alabsubtext}
%
\apar{2-8}
The feasibility of a VPL captures the notion of a network that has
good worst-case performance (since \(h\) determines the maximum number
of VPs that are needed for the compositions of any VC, and this number
is proportional to the time that the creation of that VC takes)\@. We
now define an optimal solution as a solution that does not require
much of the network resources, while maintaining this good performance
(the load on a node is proportional to the required capacity of the VP
routing tables, as well as other resources)\@.
%
\begin{alabsubtext}{Definition}{6}{}
%
Let \(h>0\) and \(\mu\geq 1\)\@. A \textsupscript{VPL}{m-m} \(\Psi\) is
\emph{\(h\)-optimal} if it is \(h\)-feasible and its load
\(\loadonnode(\Psi)\) is minimal among all other \(h\)-feasible
VPLs\@. This definition is extended in a straightforward manner to the
\((h,r)\)-optimality of a \textsupscript{VPL}{1-m} with a root~\(r\)\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Example}{1}{}
\exampfontshape
%
\begin{figure*}
%
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0065ex}
%
\begin{picture}(11164,7499)(-150,-10)
\thicklines
%
\put(1320,3157){\ellipse{1020}{1020}}
\put(4320,3157){\ellipse{1020}{1020}}
\put(1395,5932){\ellipse{1020}{1020}}
\put(4395,5932){\ellipse{1020}{1020}}
\put(7320,3082){\ellipse{1020}{1020}}
\put(10245,3082){\ellipse{1020}{1020}}
\put(4395,532){\ellipse{1020}{1020}}
\put(7845,7132){\ellipse{660}{660}}
\put(3570,5557){\ellipse{180}{480}}
\put(3780,4897){\ellipse{750}{330}}
\put(2580,3637){\ellipse{330}{750}}
\put(4755,1267){\ellipse{360}{210}}
\put(9510,2737){\ellipse{150}{300}}
\put(4785,4927){\ellipse{480}{180}}
\put(6525,3517){\ellipse{180}{480}}
\put(8025,3427){\ellipse{180}{480}}
\put(9450,3412){\ellipse{180}{480}}
\put(7485,5842){\ellipse{180}{330}}
\put(8385,5857){\ellipse{180}{330}}
\put(2070,5542){\ellipse{180}{480}}
\dottedline{\customdotgapa}(7470,5182)(8370,5182)
\texture{%
55555555 0 55555555 0 55555555 0 55555555 0 
55555555 0 55555555 0 55555555 0 55555555 0 
55555555 0 55555555 0 55555555 0 55555555 0 
55555555 0 55555555 0 55555555 0 55555555 0
}%
\shade\path(300,2962)(435,3187)(570,2962)(390,2962)(300,2962)
\shade\path(345,3667)(480,3892)(615,3667)(435,3667)(345,3667)
\shade\path(540,4942)(675,5167)(810,4942)(630,4942)(540,4942)
\shade\path(510,5347)(645,5572)(780,5347)(600,5347)(510,5347)
\shade\path(10695,3412)(10830,3637)(10965,3412)(10785,3412)(10695,3412)
\shade\path(300,3292)(435,3517)(570,3292)(390,3292)(300,3292)
\shade\path(7485,4627)(7620,4852)(7755,4627)(7575,4627)(7485,4627)
\path(1845,3157)(3795,3157)(3795,3157)
\path(4320,3682)(4320,5407)
\path(3870,5932)(1920,5932)
\path(4845,3082)(6795,3082)
\path(7845,3082)(9720,3082)
\path(4365,2632)(4395,1057)
\path(3600,5797)(2070,5782)
\path(3600,5317)(2070,5287)
%
\dottedline{\customdotgapa}(420,3082)(1648.418,3213.250)(2524.980,3363.250)
(3025.664,3556.316)(3495.000,3907.000)(3744.609,4251.531)(4010.405,5055.877)
(4110.088,5545.721)(4176.885,5785.955)(4223.906,5901.531)(4338.750,5981.219)
(4451.250,5962.469)(4535.625,5901.531)(4591.875,5770.281)
(4739.678,4980.950)(4906.523,4269.988)(4985.625,4089.812)(5014.336,4037.957)
(5278.594,3771.062)(5643.962,3630.071)(5906.755,3575.579)(7308.750,3460.750)
(9304.688,3378.250)(10205.229,3395.770)(10770.000,3457.000)
%
\dottedline{\customdotgapa}(495,3382)(1040.471,3360.577)(2172.539,3451.727)
(2231.389,3461.651)(2465.508,3506.878)(2685.820,3569.573)(2887.383,3653.362)
(3070.195,3758.245)(3234.258,3884.222)(3412.969,4071.355)(3506.133,4199.456)
(3613.945,4388.714)(3660.820,4491.253)(3682.500,4544.500)(3825.469,4931.219)
(3839.714,4973.296)(3853.154,5013.982)(3865.789,5053.277)(3877.617,5091.180)
(3931.670,5289.373)(3951.592,5393.670)(3945.000,5557.000)(3870.000,5622.625)
(3764.531,5659.539)(3616.875,5685.906)(3558.281,5692.352)
(3495.000,5697.625)(1930.400,5696.453)(1489.299,5622.332)(645.000,5407.000)
%
\dottedline{\customdotgapa}(495,3682)(634.592,3643.108)(777.744,3610.809)
(924.456,3585.101)(1024.241,3571.624)(2109.104,3597.991)(2225.515,3616.998)
(2446.003,3669.439)(2647.976,3741.802)(2831.433,3834.087)(2996.375,3946.294)
(3209.070,4151.958)(3327.722,4313.970)(3427.859,4495.904)(3654.961,5040.203)
(3717.100,5216.863)(3752.344,5346.062)(3760.898,5405.828)(3731.719,5470.281)
(3581.719,5507.781)(3523.711,5514.227)(1971.123,5455.779)
(1468.389,5346.795)(645.000,5032.000)
%
\spline(9495,2902)(7320,2857)(4620,2707)(4575,1252)
\path(7470,6382)(8370,6382)
\spline(2520,3982)(3045,4207)(3420,4957)
\spline(2595,3262)(3495,3607)(4020,4432)(4170,4882)
\spline(9435,2602)(7725,2632)(5025,2482)(4920,1282)
\spline(4530,4912)(4980,3472)(6495,3277)
\spline(5010,4942)(5265,4087)(5880,3787)(6510,3742)
\path(8040,3667)(9450,3667)
\path(7485,6007)(8370,6022)
\path(8025,3187)(9450,3172)
\path(7485,5692)(8385,5692)
%
\put(4920,6232){\makebox(0,0)[lb]{\smash{\(b\)}}}
\put(3720,2557){\makebox(0,0)[lb]{\smash{\(c\)}}}
\put(6795,2232){\makebox(0,0)[lb]{\smash{\(d\)}}}
\put(3645,832){\makebox(0,0)[lb]{\smash{\(f\)}}}
\put(8595,5707){\makebox(0,0)[lb]{\smash{virtual path}}}
\put(8595,5107){\makebox(0,0)[lb]{\smash{virtual channel}}}
\put(8595,6307){\makebox(0,0)[lb]{\smash{physical link}}}
\put(645,6232){\makebox(0,0)[lb]{\smash{\(g\)}}}
\put(795,2482){\makebox(0,0)[lb]{\smash{\(a\)}}}
\put(-100,2857){\makebox(0,0)[lb]{\smash{\(x1\)}}}
\put(-100,3277){\makebox(0,0)[lb]{\smash{\(y1\)}}}
\put(-100,3652){\makebox(0,0)[lb]{\smash{\(z1\)}}}
\put(155,5422){\makebox(0,0)[lb]{\smash{\(y2\)}}}
\put(10980,3517){\makebox(0,0)[lb]{\smash{\(x2\)}}}
\put(155,4942){\makebox(0,0)[lb]{\smash{\(z2\)}}}
\put(8595,4642){\makebox(0,0)[lb]{\smash{an end user}}}
\put(7935,4642){\makebox(0,0)[lb]{\smash{\(x2\)}}}
\put(8595,6982){\makebox(0,0)[lb]{\smash{node}}}
\put(9735,2362){\makebox(0,0)[lb]{\smash{\(e\)}}}
%
\end{picture}
}}
%
\afigcap{1}{An example for VP/VC layout}
%
\end{figure*}
%
\apar{Example 1-1}
Consider the ATM network with VPs in Figure~1, in which there are
three VCs, one between user \(x1\) and user \(x2\) (we denote it by
\(\virtchan(x1,x2)\)), one between \(y1\) and \(y2\), and one between
\(z1\) and \(z2\)\@. All VCs are composed of a concatenation of VPs
(e.g., \(\virtchan(y1,y2)\) is composed of \(\virtpath(a,b)\) and
\(\virtpath(b,g)\))\@.
%
\apar{Example 1-2}
Since the routing of cells from \(a\) to \(b\) is done on
\(\virtpath(a,b)\), there is no need for a separate entry in the VC
routing table of \(c\) for each such VC, and this remains true even if
there are many VCs that use \(\virtpath(a,b)\) as part of their route\@.
Only at \(b\) there is an entry for each of the VCs, since the
\(\virtpath(a,b)\) ends there, to determine if the VC continues into
\(\virtpath(b,d)\) (for \(\virtpath(x1,x2)\)) or into
\(\virtpath(b,g)\) (for \(\virtchan(y1,y2)\) and
\(\virtchan(z1,z2)\))\@.
%
\apar{Example 1-3}
Since each VC is composed of complete VPs, there is no way to create a
VC between \(a\) and \(c\), despite the fact that the physical network
itself is connected (hence \(\hopcount_{\mu}(a,c)=\infty\))\@.
%
\apar{Example 1-4}
Note that if \(\mu<\frac{5}{3}\), then
\(\hopcount_{\mu}(a,e)=\infty\), since the shortest path
\({d_G(a,e)=3}\) and the path induced by the VPs 
\((a,b),(b,d),(d,e) \in E_{\Psi}\) is of length~\(5\) (since
\(p=((a,b),(b,d),(d,e))\) and
\(\edgemap{I}(p)=\edgemap{I}((a,b)),\edgemap{I}((b,d)),\edgemap{I}((d,e))=(a,c,b,c,d,e)\));
If, however, \(\mu>\frac{5}{3}\), then \({\hopcount_{\mu}(a,e)=3}\)\@. As
to the load measure, \(\loadonnode(c)={\setsize{\{(a,b),(b,d),(e,f)\}}=3}\) and
\(\loadonnode(d)={\setsize{\{(b,d),(e,d),(e,f)\}}=3}\)\@.
%
\end{alabsubtext}
%
\asection{3}{Tools}
%
\apar{3-1}
Our formulation of the optimal \textsupscript{VPL}{1-m} algorithm and
its optimality proof are based on some vector notations, definitions,
and properties, which are presented in this section\@.
%
\begin{alabsubtext}{Notation}{1}{}
%
Let \(V,W\in\universe{N}^h\), \(c\in\universe{N}\), and
\(i,j\in\{1,\dots,h\}\)\@. We use the following notations:
%
\begin{itemize}
%
\item \(V[i]\)---the \(i\)th element in the vector~\(V\),
%
\item \(\vectnorm{V}{}\)---the sum of the elements \(V[i]\)
(since all elements are positive, this is the \(\mathcal{L}_{1}\) norm
of the vector, often written~\(\vectnorm{V}{1}\)),
%
\item \(\subvector{V}{i}{j}\)---the part of the vector from the
\(i\)th to the \(j\)th position (\nohyphenl{inclusive}),
%
\item \(\constvect{c\,}{i}\)---the vector \((c,\dots,c)\) of \(i\)
elements that are equal to~\(c\),
%
\item \(V\vectcat W\)---the concatenation of the vectors \(V\) and \(W\),
%
\item \(V+W\)---the vector sum of \(V\) and \(W\), and
%
\item \(V<W\)---the lexicographic comparison between vectors,
using an order in which \(V[1]\) is the least-significant component,
e.g., \((9,11,1)<(2,12,1)<(0,0,2)\)\@. The same applies for \(>\),
\(\leq\), and~\(\geq\)\@.
%
\end{itemize}
%
\end{alabsubtext}
%
\apar{3-2}
We shall need the following properties of vectors in \(\universe{N}^h\)\@.
%
\begin{sloppypar}
\begin{alabsubtext}{Lemma}{1}{}
%
Let \(L\), \(M\) be vectors in \(\universe{N}^h\) for some \(h>1\),
such that \({\vectnorm{\subvector{L}{1}{h-1}}{}\leq 1}\) and \(M\geq L\)\@.
Then \(\vectnorm{M}{}\geq\vectnorm{L}{}\)\@.
%
\end{alabsubtext}
\end{sloppypar}
%
\begin{alabsubtext}{Proof of Lemma}{1}{}
\prooffontshape
%
If \(M\geq L\), then one of the following holds:
%
\paragraph{Case 1
\protect\(\subvector{M}{1}{h-1}\geq\subvector{L}{1}{h-1}\text{\textmd{ and }}
M\protect{[}h\protect{]}=L\protect{[}h\protect{]}\protect\):}
%
Clearly
%
\[\vectnorm{\subvector{M}{1}{h-1}}{}\geq
\vectnorm{\subvector{L}{1}{h-1}}{}\]
%
hence
%
\[\vectnorm{M}{}=\vectnorm{\subvector{M}{1}{h-1}}{}+M[h]\geq
\vectnorm{\subvector{L}{1}{h-1}}{}+M[h]=\vectnorm{L}{}\]
\sentence
%
\paragraph{Case 2
\protect\(M\protect{[}h\protect{]}>L\protect{[}h\protect{]}\protect\):}
%
Then
%
\[\vectnorm{M}{}\geq M[h]\geq L[h]+1\geq
L[h]+\vectnorm{\subvector{L}{1}{h-1}}{}=\vectnorm{L}{}\]
\sentence
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 1}}
\end{alabsubtext}
%
\apar{3-3}
%
\begin{sloppypar}
\begin{alabsubtext}{Definition}{7}{}
%
A vector \(L\) is called \emph{\(k\)-nontrivial} if
\({\vectnorm{\subvector{L}{1}{k-1}}{}\leq 1}\) and
\({\vectnorm{\subvector{L}{1}{k}}{}>1}\)\@. In particular, if
\({L[1]>1}\) it is \(1\)-nontrivial, and if \(\vectnorm{L}{}\leq 1\),
then \(L\) is \hbox{\(\infty\)-}nontrivial\@. A vector is
\hbox{\(k^{(>)}\)-}nontrivial if it is \hbox{\(x\)-}nontrivial for some \(x>k\)
(similar definitions apply for \(<\), \(\leq\), and~\(\geq\))\@.
%
\end{alabsubtext}
\end{sloppypar}
%
\begin{alabsubtext}{Definition}{8}{}
%
Let \(\vecpairseq{S}\) be a sequence of vector pairs in \(\universe{N}^h\), 
\(\vecpairseq{S}=((L_{i},M_{i}))_{i=1}^s\)\@.
\(\vecpairseq{S}\)~is \emph{proper} if the following properties hold:
%
\begin{enumerate}
%
\item[P1:] \(L_{i}\leq M_{i}\) for every \(i\in\{1,\dots,s\}\), and 
%
\item[P2:] if \(i>j\), then there exists \(k>0\) such that
\(\subvector{L_j}{1}{k}\geq\subvector{L_i}{1}{k}\), \(L_j\) is
\(k\)-nontrivial, and \(L_i\) is  \(k^{(\geq)}\)-nontrivial\@.
%
\end{enumerate}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Notation}{2}{}
%
We shall need the following additional vector notations, where \(L\)
is an arbitrary vector of length \(h\),
\(\vecpairseq{S}=((L_{i},M_{i}))_{i=1}^{s}\)\@.
%
\begin{itemize}
%
\item The transformation \(\subvecinc{L}{j}\) on a vector \(L\) is
defined by: \(\subvecinc{L}{0}=L\), and
\(\subvecinc{L}{j}=
\constvect{0}{j}\vectcat(L[j+1]+1)\vectcat\subvector{L}{j+2}{h}\)
for \(j>0\)\@.
%
\item \(\leftseq{\vecpairseq{S}}=(L_{i})_{i=1}^{s}\), and
\(\rightseq{\vecpairseq{S}}=(M_{i})_{i=1}^{s}\)\@.
%
\item \(\sumvecseq((L_{i})_{i=1}^{s})=\sum_{i=1}^{s}L_{i}\)\@.
%
\item Let \(P=(p_{1},p_{2},\dots,p_{s})\) where \(0\leq p_{i}\leq h-1\)\@.
Then \(\subvecinc{\vecpairseq{S}}{P}=(\subvecinc{L_{i}}{p_{i}})_{i=1}^{s}\)\@.
%
\end{itemize}
%
\end{alabsubtext}
%
\apar{3-4}
Consider a proper sequence \(\vecpairseq{S}=((L_i,M_i))_{i=1}^s\)\@.
Clearly
\(\sumvecseq(\leftseq{\vecpairseq{S}})\leq
\sumvecseq(\rightseq{\vecpairseq{S}})\)\@. Note that the transformation
\(\subvecinc{L_{i}}{j}\) of a vector in \(\vecpairseq{S}\) increases
\(L_{i}\) lexicographically\@.
So, the sum of the \(L_{i}\) vectors, after
transforming \(\subvecinc{L_{i}}{j}\),
may become lexicographically larger than the sum of the \(M_{i}\)s\@.
That is, in some cases
\(\sumvecseq(\complsupscrstrut\subvecinc{\leftseq{S}}%
{(0,\dots,0,j,0,\dots,0)})>
\sumvecseq(\rightseq{\vecpairseq{S}})\), even though
\(\vecpairseq{S}\) is proper\@.
To solve this problem, we first show that if the total sum of values
in the \(M_{i}\) vectors
(\(\vectnorm{\sumvecseq(\rightseq{\vecpairseq{S}})}{}\))
is less than that of the \(L_{i}\) vectors, \emph{one} of the
\(L_{i}\)s can indeed be transformed without violating the overall
lexicographic order, that is:
\(\sumvecseq(\complsupscrstrut\subvecinc{\leftseq{\vecpairseq{S}}}%
{(0,\dots,0,j,0,\dots,0)})\leq
\sumvecseq(\rightseq{\vecpairseq{S}})\)\@.
%
\begin{alabsubtext}{Lemma}{2}{}
%
Let \({\vecpairseq{S}}=(L_{i},M_{i})_{i=1}^s\) be a proper sequence,
and let \(\vectnorm{\sumvecseq(\rightseq{\vecpairseq{S}})}{}<
\vectnorm{\sumvecseq(\leftseq{\vecpairseq{S}})}{}\)\@. Then there exist
integers \(0<p\leq h-1\) and \(0<k\leq s\) such that
\(\sumvecseq(\leftseq{\vecpairseq{S}})\leq
\sumvecseq(\rightseq{\vecpairseq{S}})\), where
\(P=0[k-1] \vectcat p\vectcat\constvect{0}{s-k}\)\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{2}{}
\prooffontshape
%
\begin{figure*}
%
\fbox{\parbox[t]{\textwidth}{%
%
\[
\setlength{\arraycolsep}{\customarraycolsep}
%
\begin{array}{ccccc}
%
\begin{gathered}
%
\left(
%
\begin{array}{lcl}
%
L_{1}  & \leq & M_{1}\\
 &\vdots\\
%
L_{k} & \leq & M_{k}\\
 &\vdots\\
%
L_{j} & < & M_{j}\\
 & \vdots & \\
%
L_{s} & \leq & M_{s}
%
\end{array}
%
\right)\\[\customlabelskip]
%
\mathlabel{(a)}
%
\end{gathered}
%
&
\begin{gathered}
%
\mbox{\LARGE\(\transformsto\)}\\[\customlabelskip]
%
\phantom{\mathlabel{(b)}}
%
\end{gathered}
&
%
\begin{gathered}
%
\left(
%
\begin{array}{lcl}
%
L_{1} & \leq & M_{1}\\
 & \vdots& \\
%
\subvecinc{L_{k}}{p} & \mathrel{?} & M_{k}\\
 & \vdots & \\
%
L_{j} & < & M_{j}\\
 & \vdots & \\
%
L_{s} & \leq & M_{s}
%
\end{array}
%
\right)\\[\customlabelskip]
%
\mathlabel{(b)}
%
\end{gathered}
%
&
\begin{gathered}
%
\mbox{\LARGE\(\transformsto\)}\\[\customlabelskip]
%
\phantom{\mathlabel{(b)}}
%
\end{gathered}
&
%
\begin{gathered}
%
\left(
%
\begin{array}{lcl}
%
L_{1} & \leq & M_{1}\\
 & \vdots & \\
%
\subvecinc{L_{k}}{p} & \leq & M_{k}^{\text{dir}}\\
 & \vdots & \\
%
L_{j} & \leq & M_{j}^{\text{indir}}\\
 & \vdots & \\
%
L_{s} & \leq & M_{s}
%
\end{array}
%
\right)\\[\customlabelskip]
%
\mathlabel{(c)}
%
\end{gathered}
%
\end{array}
%
\]
%
}}
%
\afigcap{2}{Transformations in Case~2 of Lemma~2}
%
\end{figure*}
%
\apar{Proof of Lemma 2-1}
Let \(L_{k}\) be the first vector in \(\leftseq{\vecpairseq{S}}\) that
is \(p\)-nontrivial for \(p<\infty\)\@. Such a choice of \(k\) exists,
since otherwise
\(\vectnorm{\sumvecseq(\leftseq{\vecpairseq{S}})}{}\leq
\vectnorm{\sumvecseq(\rightseq{\vecpairseq{S}})}{}\) by Lemma~1\@.
%
\apar{Proof of Lemma 2-2}
Clearly \(\vectnorm{\subvecinc{L_{k}}{p}}{}<\vectnorm{L_{k}}{}\)\@. If
\(\subvector{L_k}{p+1}{h}<\subvector{M_{k}}{p+1}{h}\), then
\({\subvecinc{L_{k}}{p}\leq M_{k}}\) and
\(\sumvecseq(\leftseq{\vecpairseq{S}})\leq
\sumvecseq(\rightseq{\vecpairseq{S}})\), as required by the
lemma\@. Otherwise, if
\(\subvector{L_k}{p+1}{h}=\subvector{M_{k}}{p+1}{h}\)
(and therefore \(\subvecinc{L_{k}}{p}>M_{k}\)), then two cases are
possible:
%
\paragraph{Case 1 \protect\(\text{\textmd{For every }}j>k\protect\),
\protect\(\subvector{L_{j}}{p+1}{h}=\subvector{M_{j}}{p+1}{h}\protect\):}\ \\
%
Then \(\vectnorm{L_{j}}{}\leq\vectnorm{M_{j}}{}\) since \(L_{j}\) is
\(p^{(\geq)}\)-nontrivial, and hence
\(\subvector{L}{1}{p},\subvector{M}{1}{p}\) satisfy the conditions of
Lemma~1\@. But, since \(\vectnorm{L_{i}}{}\leq\vectnorm{M_{i}}{}\)
for every \(i<k\), we have
\(\vectnorm{\sumvecseq(\leftseq{\vecpairseq{S}})}{}\leq
\vectnorm{\sumvecseq(\rightseq{\vecpairseq{S}})}{}\), contradicting
the conditions of the lemma\@.
%
\paragraph{Case 2 \protect\(\text{\textmd{There exists }}j>k
  \text{\textmd{ such that }}\subvector{L_{j}}{p+1}{h}<
  \subvector{M_{j}}{p+1}{h}\):}\ \\
%
We transform the \(M_{k}\) and \(M_{j}\) vectors so as to keep the
lexicographic order in the \(k\)th and \(j\)th pairs, without changing 
the sum \(\sumvecseq(\rightseq{\vecpairseq{S}})\), thereby proving the
lemma (refer to Figure~2)\@. The transformations are as follows\@.
%
\begin{align*}
M_{k}^{\text{dir}} &=\subvector{M_{j}}{1}{p}\vectcat(M_{k}[p+1]+1)\vectcat
\subvector{M_{k}}{p+2}{h}\\
%
M_{j}^{\text{indir}} &=\subvector{M_{k}}{1}{p}\vectcat(M_{j}[p+1]-1)\vectcat
\subvector{M_{j}}{p+2}{h}
%
\end{align*}
%
Clearly \(M_{k}+M_{j}=M_{k}^{\text{dir}}+M_{j}^{\text{indir}}\) and
therefore
\(\sum_{j=1}^{s}M_{j}=\sumvecseq(\rightseq{\vecpairseq{S}})\)\@. It is
also clear that \(\subvecinc{L_{k}}{p}\leq M_{k}^{\text{dir}}\)\@. The
lexicographic order still holds for the \(j\)th pair
(\(L_j\leq M_{j}^{\text{indir}}\)), because
\(\subvector{L_{j}}{p+1}{h}\leq\subvector{M_{j}^{\text{indir}}}{p+1}{h}\)
and \(\subvector{L_{j}}{1}{p}\leq\subvector{L_{k}}{1}{p}\leq
\subvector{M_{k}}{1}{p}=\subvector{M_{j}^{\text{indir}}}{1}{p}\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 2}}
\end{alabsubtext}
%
\apar{3-5}
We now use Lemma~2 repeatedly to show that it is possible to decrease
the total sum of values in all the \(L\) vectors
(\(\vectnorm{\sumvecseq(\leftseq{\vecpairseq{S}})}{}\)) without
increasing their total lexicographic order
(\(\sumvecseq(\leftseq{\vecpairseq{S}})\)) too much\@.
%
\begin{alabsubtext}{Lemma}{3}{}
%
Let \(\vecpairseq{S}=((L_{i},M_{i}))_{i=1}^s\) be a proper sequence\@.
Then there exists a vector of integers \(P=(p_{1},p_{2},\dots,p_{s})\)
such that the following conditions hold:
%
\begin{enumerate}
%
\item[1.] \(0\leq p_{i}\leq h-1\) for every \(i\),
%
\item[2.] \(\sumvecseq(\subvecinc{\leftseq{\vecpairseq{S}}}{P})\leq
\sumvecseq(\rightseq{\vecpairseq{S}})\), and
%
\item[3.] \(\vectnorm{\sumvecseq(\subvecinc{\leftseq{\vecpairseq{S}}}{P})}{}\leq
\vectnorm{\sumvecseq(\rightseq{\vecpairseq{S}})}{}\)\@.
%
\end{enumerate}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{3}{}
\prooffontshape
%
\apar{Proof of Lemma 3-1}
Starting with \(P=(0,\dots,0)\), we gradually increase the coordinates of
\(P\) until Condition~3 holds, while preserving Condition~2\@.
Note that for the initial \(P=(0,\dots,0)\), Condition~2 holds:
\(\sumvecseq(\subvecinc{\leftseq{\vecpairseq{S}}}{P})=
\sumvecseq(\leftseq{\vecpairseq{S}})\leq
\sumvecseq(\rightseq{\vecpairseq{S}})\)
(the left equality holds by definition of
\(\subvecinc{L_{i}}{0}\), and the right inequality is due to Property
P1 for each pair in \(\vecpairseq{S}\))\@. The transformations implied
by the changes in \(P\) may, however, violate P1 (i.e.,
\(\subvecinc{L_{i}}{p_{i}}\) may become lexicographically greater than
\(M_{i}\))\@. In order to avoid such violations (and thereby preserve
Condition~2), we use Lemma~2\@.
%
\apar{Proof of Lemma 3-2}
In this process, we have advanced toward satisfying
Condition~3, since now
\(\vectnorm{\subvecinc{L_{i}}{p_{i}}}{}\leq\vectnorm{M_{i}}{}\),
while this did not necessarily hold for \(\vectnorm{L_{i}}{}\) and
\(\vectnorm{M_{i}}{}\)\@. Before the next change in \(P\),
\(\vecpairseq{S}\) must be rearranged to remain proper\@. To this end,
the vectors in \(\vecpairseq{S}\) need to be transformed as in 
Lemma~2 to maintain Property P1\@. In addition, they may need to
be reordered so as to keep Property P2\@. However, these changes do not
alter \(\sumvecseq(\rightseq{\vecpairseq{S}})\)\@.
%
\apar{Proof of Lemma 3-3}
Since \(\vectnorm{\sumvecseq(\leftseq{\vecpairseq{S}})}{}\) decreases
each time Lemma~2 is applied, after a finite number of
applications of Lemma~2, it will become smaller than
\(\vectnorm{\sumvecseq(\rightseq{\vecpairseq{S}})}{}\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 3}}
\end{alabsubtext}
%
\asection{4}{The \protect\textsupscript{VPL}{1-m} Problem}
%
\apar{4-1}
In this section we discuss the \textsupscript{VPL}{1-m} problem on
tree networks\@. Our main result is an optimal polynomial algorithm for
this case and its proof of optimality, based on tools from the
previous section\@. Before going into the details, we mention that this
problem is hard for general topologies, assuming an unbounded stretch
factor (i.e., \(\mu=\infty\))\@. In other words, given the following
decision problem:
%
\begin{description}
%
\item[\problemlabel{Problem:}] The Optimal \textsupscript{VPL}{1-m} problem
(OPT-\textsupscript{VPL}{1-m}).
%
\item[\problemlabel{Instance:}] An undirected graph \(G=(V,E)\), a node \(r\in V\),
integers \({L,h>0}\).
%
\item[\problemlabel{Question:}] Assuming \(\mu=\infty\), does there exist
\(\Psi\), an \((h,r)\)-feasible \textsupscript{VPL}{1-m} on \(G\) such
that \(\loadonnode(\Psi)\leq L\)\@?
%
\end{description}
%
\apar{4-2}
We prove that OPT-\textsupscript{VPL}{1-m} is NP-complete\@. The
details of the proof may be found in Appendix~A.1\@.
%
\begin{alabsubtext}{Observation}{1}{}
%
It is interesting to note that the variant of
OPT-\textsupscript{VPL}{1-m} problem with fixed \(h=1\) can be solved
polynomially\@. This is done by the transformation depicted in Figure~3,
which transforms the (undirected) graph of the
\textsupscript{VPL}{1-m} problem into a (directed) flow problem\@. Each
undirected edge is replaced by five edges and two new nodes, where the
edge between these new nodes is restricted to a capacity of \(L\), and
the other edges do not have capacity restrictions\@. A new source node
is added and connected to all the original nodes except the root \(r\)
by edges of capacity \(1\)\@. The original root node is defined as the
sink\@.
%
\end{alabsubtext}
%
\begin{figure*}
%
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0045ex}
%
\begin{picture}(15017,7900)(0,-10)
\thicklines
%
\put(248,3975){\ellipse{466}{466}}
\put(2018,3960){\ellipse{466}{466}}
\put(1223,2115){\ellipse{466}{466}}
\put(1178,5790){\ellipse{466}{466}}
\put(5775,4222){\ellipse{466}{466}}
\put(7875,6547){\ellipse{466}{466}}
\put(10050,4222){\ellipse{466}{466}}
\put(7875,1672){\ellipse{466}{466}}
\path(5775,3997)(6298,2746)
\blacken\path(6150.071,2944.285)(6298.000,2746.000)(6260.786,2990.571)(6150.071,2944.285)
\path(6949,3427)(6000,4072)
\blacken\path(6232.221,3986.715)(6000.000,4072.000)(6164.766,3887.468)(6232.221,3986.715)
\path(7086,3232)(7800,1897)
\blacken\path(7633.904,2080.336)(7800.000,1897.000)(7739.720,2136.930)(7633.904,2080.336)
\path(7650,1822)(6511,2548)
\blacken\path(6745.633,2469.596)(6511.000,2548.000)(6681.134,2368.405)(6745.633,2469.596)
\path(9975,3922)(9362,2746)
\blacken\path(9419.730,2986.556)(9362.000,2746.000)(9526.141,2931.088)(9419.730,2986.556)
\path(8711,3427)(9825,4072)
\blacken\path(9825.000,4072.000)(9587.238,4003.668)(9647.366,3899.819)(9825.000,4072.000)
\path(8574,3232)(7875,1897)
\blacken\path(7933.171,2137.450)(7875.000,1897.000)(8039.481,2081.787)(7933.171,2137.450)
\path(8025,1897)(9149,2548)
\blacken\path(8971.390,2375.795)(9149.000,2548.000)(8911.247,2479.635)(8971.390,2375.795)
\path(9975,4522)(9377,5728)
\blacken\path(9537.372,5539.636)(9377.000,5728.000)(9429.863,5486.328)(9537.372,5539.636)
\path(8726,5047)(9825,4372)
\blacken\path(9589.092,4446.480)(9825.000,4372.000)(9651.895,4548.733)(9589.092,4446.480)
\path(8589,5242)(7950,6322)
\blacken\path(8123.849,6145.999)(7950.000,6322.000)(8020.573,6084.893)(8123.849,6145.999)
\path(8100,6472)(9164,5926)
\blacken\path(8923.080,5982.191)(9164.000,5926.000)(8977.866,6088.955)(8923.080,5982.191)
\path(5775,4447)(6313,5728)
\blacken\path(6275.386,5483.490)(6313.000,5728.000)(6164.748,5529.956)(6275.386,5483.490)
\path(6964,5047)(5925,4447)
\blacken\path(6102.830,4618.979)(5925.000,4447.000)(6162.840,4515.061)(6102.830,4618.979)
\path(7101,5242)(7725,6322)
\blacken\path(7656.885,6084.176)(7725.000,6322.000)(7552.981,6144.209)(7656.885,6084.176)
\path(7650,6472)(6526,5926)
\blacken\path(6715.661,6084.835)(6526.000,5926.000)(6768.094,5976.896)(6715.661,6084.835)
\path(9170,5712)(8715,5257)
\whiten\path(8842.279,5469.132)(8715.000,5257.000)(8927.132,5384.279)(8842.279,5469.132)
\path(6520,5712)(6975,5257)
\whiten\path(6762.868,5384.279)(6975.000,5257.000)(6847.721,5469.132)(6762.868,5384.279)
\path(6505,2762)(6960,3217)
\whiten\path(6832.721,3004.868)(6960.000,3217.000)(6747.868,3089.721)(6832.721,3004.868)
\path(9155,2762)(8700,3217)
\whiten\path(8912.132,3089.721)(8700.000,3217.000)(8827.279,3004.868)(8912.132,3089.721)
\path(11325,7657)(12180,7657)
\path(11940.000,7597.000)(12180.000,7657.000)(11940.000,7717.000)
\path(11325,6772)(12180,6772)
\whiten\path(11940.000,6712.000)(12180.000,6772.000)(11940.000,6832.000)(11940.000,6712.000)
\path(11325,5872)(12210,5872)
\blacken\path(11970.000,5812.000)(12210.000,5872.000)(11970.000,5932.000)(11970.000,5812.000)
%
\put(3150,3900){\makebox(0,0)[lb]{{\Huge\(\transformsto\)}}}
%
\path(353,4185)(1043,5595)
\path(1373,5655)(1958,4200)
\path(2003,3735)(1358,2280)
\path(263,3735)(1043,2265)
\path(7875,397)(7875,1372)
\path(7799.500,1129.000)(7875.000,1372.000)(7950.500,1129.000)
\spline(7665,232)(5790,1477)(5625,3997)
\path(5700.553,3761.433)(5625.000,3997.000)(5580.809,3753.593)
\spline(8055,232)(9885,1447)(10200,3997)
\path(10230.124,3751.455)(10200.000,3997.000)(10111.029,3766.166)
%
\put(1410,6052){\makebox(0,0)[lb]{\smash{root}}}
\put(8220,6952){\makebox(0,0)[lb]{\smash{sink}}}
\put(8400,97){\makebox(0,0)[lb]{\smash{source}}}
\put(12500,7537){\makebox(0,0)[lb]{\smash{edge, capacity \(1\)}}}
\put(12500,6652){\makebox(0,0)[lb]{\smash{edge, capacity \(L\)}}}
\put(12500,5767){\makebox(0,0)[lb]{\smash{edge, capacity \(\infty\)}}}
%
\path(7650,397)(8025,397)(8025,22)(7650,22)(7650,397)
\path(6511,2557)(6549,2700)(6444,2805)(6301,2767)(6263,2624)(6368,2519)(6511,2557)
\path(7164,3225)(7202,3368)(7097,3473)(6954,3435)(6916,3292)(7021,3187)(7164,3225)
\path(7164,5040)(7202,5183)(7097,5288)(6954,5250)(6916,5107)(7021,5002)(7164,5040)
\path(6534,5745)(6572,5888)(6467,5993)(6324,5955)(6286,5812)(6391,5707)(6534,5745)
\path(8754,5040)(8792,5183)(8687,5288)(8544,5250)(8506,5107)(8611,5002)(8754,5040)
\path(9384,5745)(9422,5888)(9317,5993)(9174,5955)(9136,5812)(9241,5707)(9384,5745)
\path(8709,3240)(8747,3383)(8642,3488)(8499,3450)(8461,3307)(8566,3202)(8709,3240)
\path(9339,2565)(9377,2708)(9272,2813)(9129,2775)(9091,2632)(9196,2527)(9339,2565)
%
\end{picture}
}}
%
\afigcap{3}{Transforming the \protect\textsupscript{VPL}{1-m} problem
into a flow problem}
%
\end{figure*}
%
\apar{4-3}
We now present a polynomial-time optimal solution for \textsupscript{VPL}{1-m}, assuming
\(\mu=1\) and a tree network\@. These restrictions still allow a variety
of applications for the problem\@. In particular, this restricted
\textsupscript{VPL}{1-m} problem is used as a building block for solving the \textsupscript{VPL}{m-m}
problem\@. In addition, it has practical applications of its own, in
the field of client-server applications over ATM \cite{cj96-04-20}\@. The
problem also serves as a sufficiently complex case to allow for a
presentation of nontrivial upper and lower bound results, using
techniques which we expect to be basic in similar future studies\@.
%
\asubsection{4.1}{The Algorithm}
%
\apar{4.1-1}
We devise a greedy algorithm that produces an optimal
\textsupscript{VPL}{1-m} for any tree\@. This algorithm is an iterative
process in which the minimal load is guessed by the
\algo{informal}{}{\(\prog{\idr{main}}\)} procedure, which calls the
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} procedure with
the guessed load as a parameter\@. The
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} procedure tries
to construct a layout under the given load constraint, and informs the
\algo{informal}{}{\(\prog{\idr{main}}\)} if the guess enabled the
construction of the layout\@. Using this information,
\algo{informal}{}{\(\prog{\idr{main}}\)} increases or decreases its
guess, until it achieves a minimal guess for which
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} succeeds\@. Let
\algo{informal}{}{\(\idr{vectarray}\)} represent the type
\algo{informal}{}{\(\kwd{array}[V(T)]\kwd{ of }\universe{N}^{h}\)}\@.
%
\begin{algorithm}{informal}{}
%
\item[0.] \kwd{procedure} \(\prog{\idr{main}}(h\oftype\universe{N},\;T\oftype\text{tree},\;\idr{root}\oftype V(T)\))
%
\item[1.] \progind\kwd{var}
  \(\idr{L1},\idr{L2}\oftype\idr{vectarray}\)
%
\item[2.] \progind\kwd{find}
\(\loadonnode_{\text{max}}\in\{1,\dots,\setsize{V(T)}\}\) \kwd{such that}
%
\item[3.] \progind\progind
\(\progfunc{\idr{find\_layout}}(h,T,\idr{root},\loadonnode_{\text{max}},\idr{L1})=
\progstat{success}\) \kwd{and}
%
\item[4.] \progind\progind\(\progfunc{\idr{find\_layout}}(h,T,\idr{root},\loadonnode_{\text{max}}-1,\idr{L2})=\progstat{failure}\)
%
\item[5.] \progind\(\progfunc{\idr{construct\_layout}}(\idr{root},\idr{L1})\)
%
\item[6.] \kwd{end procedure} \(\prog{\idr{main}}\)
%
\end{algorithm}
%
\apar{4.1-2}
In the \algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} procedure,
we view the tree~\(T\) as rooted at \(root\)\@. The procedure starts
from the leaves of the tree and advances toward the root\@. For each
node~\(v\) it maintains the number of VPs that go through \(v\) (and
contribute to its load)\@. This number is kept in a vector
\(L_{v}\in\universe{N}^h\), where \(L_v[1]\) holds the number of VPs
that serve only as a first hop from some descendant, and \(L_{v}[i]\)
holds the number of VPs that are an \(i\)th hop\footnote{The shortest
path, in terms of VPs, from \(x\) toward the root includes the VP as
the \(i\)th VP from it\@.} for some descendant~\(x\), but not an
\((i+1)\)th hop for any descendant\@.
%
\apar{4.1-3}
Specifically, \algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)}
creates a first-hop VP for each leaf (at line~4)\@. At an internal node
\(v\), the vector \(L_{v}\), of VPs is equal to the vector sum of all
the VPs that arrive at it from all its sons, plus one additional
first-hop VP from \(v\) toward the root (at line~14)\@. If this vector
is too big (i.e., \(\vectnorm{L_{v}}{}\) exceeds the current load
constraint at line~15), then the VPs that go through \(v\) are
reduced by stopping some of them at the sons of \(v\) (hence turning
the VP that starts at that son from a first-hop VP to an \((i+1)\)th
hop VP), by applying the transformation in Figure~4 (at lines 16--21)\@.
%
\begin{algorithm}{informal}{}
%
\item[0.] \kwd{function}
\(\progfunc{\idr{find\_layout}}(h\oftype\universe{N},\;
\idr{root}\oftype V(T),\;
\loadonnode_{\text{max}}\oftype\universe{N},\;
\text{\kwd{var} }\idr{L}\oftype\idr{vectarray})\)
%
\item[1.] \progind\kwd{returns} \(\{\progstat{success},\progstat{failure}\}\)
%
\item[2.] \progind\comment{\(\idr{L}_{v}\) indicates the entry of \(\idr{L}\)
  indexed by \(v\)}
%
\item[3.] \progind\kwd{for all} \(w\in V(T)\)
%
\item[4.] \progind\progind\kwd{if} \(w\text{ is a leaf}\) \kwd{then}
\(L_{w}\assigned(1,0,\dots,0)\)
%
\item[5.] \progind\progind\progind\kwd{else}
\(L_{w}\assigned\progconst{\idr{UNDEFINED}}\)
%
\item[6.] \progind\progind\kwd{end if}
%
\item[7.] \progind\kwd{end for}
%
\item[8.] \progind\kwd{loop} \(\idr{forever}\) \proglab{outer}
%
\item[9.] \progind\progind\kwd{if} \(v=root\) \kwd{then}
\kwd{return} \(\progstat{success}\) \kwd{end if}
%
\item[10.] \progind\progind\kwd{find} \(v\in V(T)\) \kwd{such that}
%
\item[11.] \progind\progind\progind\(L_{v}=\progconst{\idr{UNDEFINED}}\)
\kwd{and}
%
\item [12.] \progind\progind\progind
\(\text{for all }x\in\progfunc{\idr{Sons}}(v)\text{, }L_{x}\neq
\progconst{\idr{UNDEFINED}}\)
%
\item[13.] \progind\progind\kwd{loop} \(\idr{forever}\) \proglab{inner}
%
\item[14.] \progind\progind\progind
\(L_{v}\assigned\sum_{s\in\progfunc{\idr{Sons}}(v)}L_{s}+(1,0,\dots,0)\)
%
\item[15.] \progind\progind\progind\kwd{if}
\(\vectnorm{L_v}{}\leq\loadonnode_{\text{max}}\) \kwd{then}
\kwd{exit loop} \proglab{inner} \kwd{end if}
%
\item[16.] \progind\progind\progind \kwd{find}
\(s\in\progfunc{\idr{Sons}}(v)\), \(i\in\{1,\dots,h-1\}\) \kwd{such that}
%
\item[17.] \progind\progind\progind\progind
\(\vectnorm{\subvector{L_{s}}{1}{i}}{}>1\) \kwd{and}
%
\item[18.] \progind\progind\progind\progind
\(\text{for all }s'\in\progfunc{\idr{Sons}}(v)\setminus \{s\}\text{, }
\subvector{L_{s}}{1}{i}\geq\subvector{L_{s'}}{1}{i}\)
\comment{lexicographic}
%
\item[19.] \progind\progind\progind\progind
\(\text{for all }s'\in\progfunc{\idr{Sons}}(v)\text{, }
\vectnorm{\subvector{L_{s'}}{1}{i-1}}{}\leq 1\)
%
\item[20.] \progind\progind\progind
\kwd{if} \(\text{no such }i,s\text{ exist}\) \kwd{then} 
\kwd{return} \(\progstat{failure}\) \kwd{end if}
%
\item[21.] \progind\progind\progind
\(L_{s}\assigned
\constvect{0}{i}\vectcat(L_{s}[i+1]+1)\vectcat\subvector{L_{s}}{i+2}{h}\)
%
\item[] \progind\progind\progind\progind
\comment{transform \(L_{s}\) to \(\subvecinc{L_{s}}{i+1}\)}
%
\item[22.] \progind\progind \kwd{end loop} \proglab{inner}
%
\item[23.] \progind \kwd{end loop} \proglab{outer}
%
\item[24.] \kwd{end function} \(\prog{\idr{find\_layout}}\)
%
\end{algorithm}
%
\begin{figure*}
%
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0065ex}
%
\begin{picture}(10268,6607)(0,-10)
\thicklines
%
\put(5150,4500){\makebox(0,0)[lb]{{\Huge\(\transformsto\)}}}
%
\put(3255.795,6569.815){\arc{2851.626}{0.0476}{3.1466}}
\put(8280.795,6569.815){\arc{2851.626}{0.0476}{3.1466}}
\put(2820,3472){\ellipse{2370}{2370}}
\put(2880,3847){\blacken\ellipse{150}{150}}
\put(2880,3847){\ellipse{150}{150}}
\put(8205,3472){\ellipse{2370}{2370}}
\put(8250,3862){\blacken\ellipse{150}{150}}
\put(8250,3862){\ellipse{150}{150}}
\put(8520,3472){\blacken\ellipse{90}{90}}
\put(8520,3472){\ellipse{90}{90}}
\put(8685,3472){\blacken\ellipse{90}{90}}
\put(8685,3472){\ellipse{90}{90}}
\put(8850,3457){\blacken\ellipse{90}{90}}
\put(8850,3457){\ellipse{90}{90}}
\put(9030,3472){\blacken\ellipse{90}{90}}
\put(9030,3472){\ellipse{90}{90}}
\put(1605,367){\ellipse{720}{720}}
\put(2985,367){\ellipse{720}{720}}
\put(4365,367){\ellipse{720}{720}}
\put(7140,367){\ellipse{720}{720}}
\put(8520,367){\ellipse{720}{720}}
\put(9900,367){\ellipse{720}{720}}
\path(2880,3802)(3090,5947)
\path(8250,3817)(8475,5962)
\dashline[200]{60.000}(3465,5662)(2685,5782)
\dashline[200]{60.000}(8895,5737)(8115,5857)
\dashline[200]{60.000}(8385,2992)(9585,3232)
\dashline[200]{60.000}(2910,5062)(2175,4957)
\dashline[200]{60.000}(3165,4897)(3810,4687)
\dashline[200]{60.000}(8220,4912)(7455,5017)
\spline(2520,5632)(2460,3472)(1485,412)
\spline(2745,5557)(2730,3442)(2985,487)
\spline(2625,5602)(2580,3472)(1680,307)
\spline(7815,5662)(7830,3487)(7020,442)
\spline(8055,5632)(8100,3442)(8520,502)
\spline(7935,5632)(7965,3472)(7230,382)
\spline(3375,5452)(3255,3367)(1800,247)
\spline(3585,5332)(3405,3337)(4230,427)
\spline(3675,5302)(3495,3352)(4455,442)
\spline(8670,3472)(8715,2677)(8640,487)
\spline(8505,3472)(8610,2677)(7350,322)
\spline(8850,3502)(8865,2722)(9780,337)
\spline(9030,3487)(9000,2752)(9900,412)
\spline(3480,5437)(3345,3367)(3135,457)
%
\put(2370,6200){\makebox(0,0)[lb]{\smash{\(j=1\)}}}
\put(7860,6200){\makebox(0,0)[lb]{\smash{\(j=i+1\)}}}
\put(9585,3382){\makebox(0,0)[lb]{\smash{\(j\leq i\)}}}
\put(1500,5032){\makebox(0,0)[lb]{\smash{\(j>i\)}}}
\put(3945,4597){\makebox(0,0)[lb]{\smash{\(j\leq i\)}}}
\put(6500,4987){\makebox(0,0)[lb]{\smash{\(j>i\)}}}
\put(840,3322){\makebox(0,0)[lb]{\smash{Son}}}
\put(50,5632){\makebox(0,0)[lb]{\smash{\shortstack[r]{Overloaded\\ node}}}}
%
\end{picture}
}}
%
\afigcap{4}{The transformation on an overloaded node \protect\(v\protect\):
  \protect\(L_{v}\transformsto\subvecinc{L_{v}}{i+1}\protect\)}
%
\end{figure*}
%
\apar{4.1-4}
A partial intuition behind this transformation is that it is better to
stop VPs that serve as a \(j\)th hop for the lowest possible \(j\), as
this does not increase the vector \(L_{v}\) too much in its lexicographic
order\@. A part of this transformation is, however, nonintuitive, and
stems directly from needs of the proof of optimality\@.
%
\apar{4.1-5}
The \algo{informal}{}{\(\prog{\idr{main}}\)} procedure relies on
\algo{informal}{}{\(\prog{\idr{construct\_layout}}\)} for the actual
creation of the \textsupscript{VPL}{1-m} from the set of vectors in
\algo{informal}{}{\(\idr{L}\)}\@. This procedure is activated for a node
\(v\) and recursively creates VPs for all the nodes in the subtree
rooted at \(v\)\@. The code of
\algo{informal}{}{\(\prog{\idr{construct\_layout}}\)} is
straightforward, yet lengthy and involved, and is omitted in this
paper\@. For similar reasons, we also omit the proof of correctness of
the algorithm\@. Similar code and proofs may be found
in~\cite{cj96-04-12}\@.
%
\asubsection{4.2}{Proof of Optimality}
%
\apar{4.2-1}
We prove the solution that
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} produces is
optimal for every given tree and \(h\), thereby implicitly proving a
lower bound for the
\textsupscript{VPL}{1-m}\ problem\@. The main lemma is Lemma~6, in which
the solution \(\setof{L_{v}}{v\in V}\) of
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} is compared to an
arbitrary minimal solution with a vector representation
\(\setof{M_{v}}{v\in V}\)\@. To this end, we first prove (in Lemma~5)
that every minimal solution indeed has a vector representation with
some desired properties\@. In this representation,
\(\vectnorm{W_{v}}{}\) is the load on node \(v\)\@. Using the tools in
Section~3, in particular Lemma~3, we prove (by induction) that at
every node \(v\), \(L_{v}\leq M_{v}\) and
\(\vectnorm{L_{v}}{}\leq\vectnorm{M_{v}}{}\), thereby proving that
the solution of \algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)}
has minimal load (and is thus optimal)\@. The simple case for the proof
is when \(v\) is not overloaded, in which case \(L_{v}=\sum_{s\in
Sons(v)}L_{s}+(1,0,\dots,0)\), and the inductive claim easily follows,
assuming it holds for each son of \(v\)\@. For an overloaded node, the
load vectors of the sons are arranged in the order that they are
chosen by \algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} at
lines~15--16\@. This order is reflected by Property P2 of a proper sequence
(see Definition~8)\@. Then, they are lexicographically compared to the
respective \(M\) vectors\@.
%
\apar{4.2-2}
Thus, before applying transformations on any son of \(v\), we have
\({L_{i}\leq M_{i}}\), \(i=1,\dots,s\)\@. Using Lemma~3, we show
that after several transformations the total load at \(v\),
\(\vectnorm{\sumvecseq(\leftseq{\vecpairseq{S}})}{}\), decreases at
least to the level of the given optimal solution
(\(\vectnorm{\sumvecseq(\rightseq{\vecpairseq{S}})}{}\)), while
maintaining its property of being lexicographically minimal\@.
%
\apar{4.2-3}
The above sketch is formalized as follows\@.
%
\begin{alabsubtext}{Definition}{9}{}
%
Let \(\maxhopcount(\psi)\) denote the maximal hop count for which
\(\psi\) serves from some node to the root (this is the value
\(j=i+1\) assigned to the VP starting at the son in Figure~4\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Definition}{10}{}
%
Given \(h>0\), a \textsupscript{VPL}{1-m} is \emph{\((h,r)\)-minimal}
if it is \((h,r)\)-feasible and the deletion of a VP
\(\psi\in E_{\Psi}\) yields a \textsupscript{VPL}{1-m} that is not
\((h,r)\)-feasible\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Lemma}{4}{}
%
In a minimal \textsupscript{VPL}{1-m}, there exists a unique VP
\(\psi_{v}\) for every node \(v\) that starts at \(v\) toward the root\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{4}{}
\prooffontshape
%
Assuming two such VPs \(\psi_{1}\) and \(\psi_{2}\) exist in a minimal
\textsupscript{VPL}{1-m}, consider the paths \(p_{i}\) (\(i=1,2\))
from \(v\) to the root that start with \(\psi_{i}\)\@. Without loss of
generality, \(p_{1}\) is not longer than \(p_{2}\) (in terms of
VP-hops)\@. Therefore, we can remove \(\psi_{2}\) from the
\textsupscript{VPL}{1-m} without damaging its feasibility,
contradicting the minimality assumption\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 4}}
\end{alabsubtext}
%
\apar{4.2-4}
Note that the previous lemma implies that the virtual graph \(G_{\Psi}\)
of a minimal \textsupscript{VPL}{1-m} on a tree, is a tree as well\@.
%
\begin{alabsubtext}{Lemma}{5}{}
%
Given \(h>0\), let \(T\) be a tree rooted at \(r\)\@. Every \((h,r)\)-minimal
\textsupscript{VPL}{1-m} on \(T\) can be represented by a set of
vectors \(\setof{M_{v}\in\universe{N}^h}{v\in V(T)}\), such that for
every node \(v\), the following conditions hold:
%
\begin{enumerate}
%
\item[1.] \(\loadonnode(v)=\vectnorm{M_{v}}{}\),
%
\item[2.] if \(v\) is a leaf then \(M_{v}=(1,0,\dots,0)\), and
%
\item[3.] \(M_{v}\geq\sum_{s\in Sons(v)}M_{s}+(1,0,\dots,0)\)\@.
%
\end{enumerate}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{5}{}
\prooffontshape
%
Let \(T_{v}\) denote the set of nodes in the subtree below \(v\)\@.
Define \(M_{v}\) for a node \(v\)~by
%
\[M_{v}[i]=\setsize{\setof{\psi\in E_{\Psi}}{v\in\psi\logicand\maxhopcount(\psi)=i}}\]
\sentence
%
Condition~2 is trivially satisfied\@. Condition~1 is satisfied since
each VP that includes the node \(v\) contributes one to a single
\(M_{v}[i]\) (according to the value of \(\maxhopcount(\psi)\)), hence
\(\loadonnode(v)=\vectnorm{M_{v}}{}\)\@. To prove Condition~3, let
\(\psi_{v}\) be the VP starting at \(v\)\@. Note that if
\(\hopcount(\psi_v) = 1\) then no VP stops at \(v\), and every VP
that loads a son of \(v\) loads \(v\) as well, which has an additional
load incurred by \(\psi_{v}\), hence
\(M_{v}=\sum_{s\in Sons(v)}M_{s}+(1,0,\dots,0)\)\@. If
\(\hopcount(\psi_{v})=i>1\) then a VP \(\psi\) that stops at \(v\) has
\(\hopcount(\psi)\leq i-1\), hence
\(\subvector{M_{v}}{i}{h}=
\sum_{s\in Sons(v)}\subvector{M_{s}}{i}{h}+(1,0,\dots,0)\) and
\(M_v>\sum_{s\in Sons(v)}M_{s}+(1,0,\dots,0)\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 5}}
\end{alabsubtext}
%
\begin{alabsubtext}{Lemma}{6}{}
%
{\sloppy
Given \({h>0}\), if there exists an \((h,r)\)-feasible
\textsupscript{VPL}{1-m} \(\Psi\) with \({\loadonnode(\Psi)\leq X}\) for
some \({X>0}\) with a vector representation
\(\setof{M_{v}}{v\in V(T)}\), then for every node \(v \ne r\) the
following holds:
%
\begin{itemize}
%
\item If \(\loadonnode_{\text{max}}=X\) then \algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} does not return
\(\progstat{failure}\) while handling \(v\), and
%
\item the vector \(L_{v}\) produced by \algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} satisfies
\(L_{v}\leq M_{v}\)\@.
%
\end{itemize}
}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{6}{}
\prooffontshape
%
\apar{Proof of Lemma 6-1}
We use induction on the height \(H\) of the subtrees of~\(T\)\@.
%
\paragraph{Basis.}
%
\apar{Proof of Lemma 6-2}
For a tree of height \({H=0}\) (i.e., a leaf),
it is clear that \(L_{v}=M_{v}=(1,0,\dots,0)\)\@. 
%
\paragraph{Induction step.}
%
\apar{Proof of Lemma 6-3}
Assume that the claim holds for subtrees of height at most \(H-1\),
and let \(v\) be a node such that \(T_{v}\) is of height \(H\)\@. By
the induction hypothesis,
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} does not return
\(\progstat{failure}\) for every son \(s\) of \(v\) and
\({L_{s}\leq M_{s}}\)\@. Let
\(L'_{v}=\sum_{s\in Sons(v)}L_{s}+(1,0,\dots,0)\)\@.
%
\apar{Proof of Lemma 6-4}
If \(\vectnorm{L'_{v}}{}\leq X\) then
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} will continue all
VPs through \(v\) (no transformations are performed), in which case,
(1) it does not return \(\progstat{failure}\) while handling \(v\),
and (2) the vector
\(L_{v}=L'_{v}\leq\sum_{s\in Sons(v)}M_{s}+(1,0,\dots,0)\leq M_{v}\)\@.
%
\apar{Proof of Lemma 6-5}
The case when \(\vectnorm{L'_{v}}{}>X\) is proven as follows\@.
Arrange the load vectors of the sons of \(v\) in the order they are
chosen at lines~16--19 (which is the order determined by Property P2 of
Definition~8), and add a pair of \((1,0,\dots,0)\) vectors to this
sequence\@. The sequence that includes these load vectors and the
corresponding \(M\) vectors is proper\@.
%
\begin{eqnarray*}
%
(1,0,\dots,0) & \leq & (1,0,\dots,0)\\
%
L_{1} &\leq & M_{1}\\
%
L_{2} &\leq & M_{2}\\
%
 & \vdots & \\
%
L_{s} & \leq & M_{s} 
%
\end{eqnarray*}
%
\apar{Proof of Lemma 6-6}
By Lemma~3, there exists a vector \(P=(p_{1},\dots,p_{s})\) of
integers \(0\leq p_{i}\leq h-1\) such that
\(\sumvecseq(\subvecinc{\leftseq{\vecpairseq{S}}}{P})\leq
\sumvecseq(\rightseq{\vecpairseq{S}})\) and
\(\vectnorm{\sumvecseq(\subvecinc{\leftseq{\vecpairseq{S}}}{P})}{}\leq
\vectnorm{\sumvecseq(\rightseq{\vecpairseq{S}})}{}\)\@. Note that
\(\sumvecseq(\subvecinc{\leftseq{\vecpairseq{S}}}{P})\) is the value
of the vector \(L_{v}\) after some finite number of iterations in the
internal loop of \algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)}
for node \(v\)\@. The only way that
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} may return
\(\progstat{failure}\) is if no son that satisfies the conditions of
lines~16--19 is found\@. In this case, all sons \(s\) have
\(\vectnorm{\subvector{L_{s}}{1}{h-1}}{}\leq 1\)\@. By
Lemma~1, \(\vectnorm{L_{s}}{}\leq\vectnorm{M_s}{}\) and hence
\(X<\vectnorm{L'_{v}}{}\leq
\vectnorm{\sumvecseq(\rightseq{\vecpairseq{S}})}{}\)---which is a
contradiction to the feasibility of the given solution, since by
Lemma~5
\(\vectnorm{\sumvecseq(\rightseq(\vecpairseq{S}))}{}\leq
\vectnorm{M_{v}}{}\)\@. Therefore we get
\(\sumvecseq(\subvecinc{\leftseq(\vecpairseq{S})}{P})\leq X\) and
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} finishes handling
\(v\) without returning \(\progstat{failure}\) with \(L_{v}\leq M_{v}\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 6}}
\end{alabsubtext}
%
\apar{4.2-5}
The theorem that concludes the proof is:
%
\begin{alabsubtext}{Theorem}{1}{}
%
Given \(h>0\), the \algo{informal}{}{\(\prog{\idr{main}}\)} procedure
finds an \((h,r)\)-optimal
\textsupscript{VPL}{1-m} for any given tree \(T\) with \(N\) nodes
rooted at \(r\), in \(\orderof{hN\log_{2}N}\) time\@.
%
\end{alabsubtext}
\sentence
%
\begin{alabsubtext}{Proof of Theorem}{1}{}
\prooffontshape
%
\apar{Proof of Theorem 1-1}
By Lemma~6, \algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} will
successfully handle each son of \(r\) if
\(\loadonnode_{\text{max}}\) implies a feasible solution\@.
%
\apar{Proof of Theorem 1-2}
It remains to show that
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} does not fail for
the root \(r\)\@. This proof is identical to the induction step of
Lemma~6, except that the \((1,0,\dots,0)\) vectors are not added as
part of the list (since no new VP starts at the root \(r\))\@. Hence,
Lemma~3 is applied on the load vectors \(L_{i}\) produced by
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} for the sons of
\(r\) and on the load vectors \(M_{i}\) for those sons in some other
\textsupscript{VPL}{1-m}\@.
%
\apar{Proof of Theorem 1-3}
Therefore, \algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} will
return \(\progstat{success}\) after handling the root (at
line~9)\@. It also returns a feasible layout that obeys
\(\loadonnode_{\text{max}}\)\@. Since
\algo{informal}{}{\(\prog{\idr{main}}\)} finds the minimal value for
\(\loadonnode_{\text{max}}\) for which
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} returns
\(\progstat{success}\), it returns the optimal
\textsupscript{VPL}{1-m}\@.
%
\apar{Proof of Theorem 1-4}
As to the time complexity of this algorithm, the search for the optimal
\(\loadonnode_{\text{max}}\), done by
\algo{informal}{}{\(\prog{\idr{main}}\)}, involves \(\log_{2}N\)
steps (by means of a binary search in the range \(1,\dots,N\) for
\(\loadonnode_{\text{max}}\))\@. In each such step,
\algo{informal}{}{\(\progfunc{\idr{find\_layout}}\)} is
activated and scans the tree bottom up, during which time each node
\(v\) is chosen once (at line~10) as the current node\@. Each node may
also be chosen up to \(h\) times (at line~16) as a son to be
transformed, since each transformation of \(L_{v}\) increases the
number of zeros in it by at least one, and \(L_{v}\) has \(h\) values\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 1}}
\end{alabsubtext}
%
\apar{4.2-6}
The above algorithm does not imply a numerical bound of the load
incurred by the layout; however, using a result from \cite{cj96-04-13},
it is easy to derive such a bound\@.
%
\begin{alabsubtext}{Lemma}{7}{}
%
For every tree network \(T\), the \textsupscript{VPL}{1-m} produced by
\algo{informal}{}{\(\prog{\idr{main}}\)} obeys
\(\loadonnode(\Psi)\leq hN^{\frac{1}{h}}\)\@. 
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{7}{}
\prooffontshape
%
Since \algo{informal}{}{\(\prog{\idr{main}}\)} produces an optimal
layout, it produces a better layout than the one suggested by
\cite{cj96-04-13} for which the load obeys
\(\loadonnode(\Psi)\leq hN^{\frac{1}{h}}\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 7}}
\end{alabsubtext}
%
\asection{5}{The \protect\textsupscript{VPL}{m-m} Problem}
%
\apar{5-1}
In this section we use the algorithm for \textsupscript{VPL}{1-m} to
solve \textsupscript{VPL}{m-m}, exemplifying our motivation for the
definition of \textsupscript{VPL}{1-m}\@. But first we note that the
\textsupscript{VPL}{m-m} problem is a hard problem as well, by proving
it is NP-complete for any odd hop count\@. The details of the proof may
be found in Appendix~A.2\@.
%
\asubsection{5.1}{A Solution for General Graphs}
%
\apar{5.1-1}
We now present a suboptimal construction scheme, based on a technique
of \cite{cj96-04-02}, for the construction of ``regional routing schemes''
(used for regular routing problems)\@.
%
\apar{5.1-2}
The scheme is based on a clustering technique, which yields connected
overlapping subgraphs of a given graph, such that each pair of nodes
with distance less than a given integer \(\delta\) may be found
together in at least one cluster\@. In each cluster we choose a center
(i.e., the node that is closest to all the other nodes of the
cluster), construct a breadth-first search tree to the center, and
connect all the other nodes of the cluster to it by a
\textsupscript{VPL}{1-m} with \(\mu=1\) and \(h'=\frac{h}{2}\) (using
the greedy algorithm of the previous section)\@. Clearly, every pair of
nodes whose distance is less than \(\delta\) may be connected using no
more than \(h\) hops via the pivot of their common cluster\@.
%
\apar{5.1-3}
We repeat this scheme for increasing parameter \(\delta\) (until the
algorithm yields one cluster that includes the whole network)\@. To
minimize the stretch factor \(\mu\), each pair is connected using the
\textsupscript{VPL}{1-m} of the smallest common cluster\@. Refer to
Figure~5 for a graphic demonstration of this scheme\@.
%
\begin{figure*}
%
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0065ex}
%
\begin{picture}(10472,6206)(0,-10)
\thicklines
%
\put(4320,2307){\ellipse{2130}{2130}}
\put(5040,3987){\ellipse{2130}{2130}}
\put(2055,3867){\ellipse{2130}{2130}}
\put(1815,2412){\ellipse{2130}{2130}}
\put(945,2352){\ellipse{180}{180}}
\texture{%
55555555 0 55555555 0 55555555 0 55555555 0 
55555555 0 55555555 0 55555555 0 55555555 0 
55555555 0 55555555 0 55555555 0 55555555 0 
55555555 0 55555555 0 55555555 0 55555555 0
}%
\put(1785,2412){\shade\ellipse{180}{180}}
\put(1785,2412){\ellipse{180}{180}}
\put(1950,1617){\ellipse{180}{180}}
\put(1530,4137){\ellipse{180}{180}}
\put(4725,4182){\ellipse{180}{180}}
\put(3435,5412){\shade\ellipse{210}{210}}
\put(3435,5412){\ellipse{210}{210}}
\put(4365,2292){\shade\ellipse{150}{150}}
\put(4365,2292){\ellipse{150}{150}}
\put(5220,4017){\shade\ellipse{150}{150}}
\put(5220,4017){\ellipse{150}{150}}
\put(6060,2547){\shade\ellipse{150}{150}}
\put(6060,2547){\ellipse{150}{150}}
\put(2910,567){\shade\ellipse{150}{150}}
\put(2910,567){\ellipse{150}{150}}
\put(2085,3897){\shade\ellipse{150}{150}}
\put(2085,3897){\ellipse{150}{150}}
\put(810,3642){\shade\ellipse{150}{150}}
\put(810,3642){\ellipse{150}{150}}
\path(1269.256,2175.671)(1020.000,2262.000)(1193.902,2063.659)
\dashline{90.000}(1020,2262)(1845,1707)
\path(1595.744,1793.329)(1845.000,1707.000)(1671.098,1905.341)
\path(1903.570,4194.689)(1650.000,4122.000)(1906.324,4059.717)
\dashline{90.000}(1650,4122)(4590,4182)
\path(4336.430,4109.311)(4590.000,4182.000)(4333.676,4244.283)
\path(1330.538,2434.535)(1080.000,2352.000)(1338.561,2299.774)
\path(1080,2352)(1135.821,2355.227)(1187.755,2358.024)(1235.978,2360.391)
(1280.665,2362.328)(1321.992,2363.834)(1360.134,2364.909)(1427.565,2365.770)
(1484.363,2364.909)(1531.932,2362.328)(1605.000,2352.000)
\path(1605,2352)(1655.046,2335.432)(1707.892,2313.278)
(1754.293,2287.985)(1785.000,2262.000)
\path(1785,2262)(1813.010,2222.622)(1837.486,2177.969)(1858.873,2126.393)
(1877.614,2066.246)(1894.153,1995.882)(1901.735,1956.352)(1908.934,1913.651)
(1915.805,1867.571)(1922.402,1817.906)(1928.782,1764.451)(1935.000,1707.000)
\path(1841.625,1953.703)(1935.000,1707.000)(1975.909,1967.591)
\path(1677.338,4433.248)(1560.000,4197.000)(1778.853,4344.256)
\path(1560,4197)(1620.579,4265.851)(1679.292,4332.058)(1736.195,4395.676)
(1791.350,4456.762)(1844.814,4515.372)(1896.647,4571.562)(1946.908,4625.387)
(1995.655,4676.905)(2042.948,4726.172)(2088.845,4773.243)(2133.407,4818.174)
(2176.691,4861.022)(2218.756,4901.844)(2259.663,4940.694)(2299.469,4977.630)
(2338.234,5012.708)(2412.875,5077.511)(2484.060,5135.554)(2552.259,5187.286)
(2617.946,5233.156)(2681.591,5273.613)(2743.667,5309.107)(2804.646,5340.086)
(2865.000,5367.000)
\path(2865,5367)(2913.953,5379.021)(2967.648,5389.164)(3025.384,5397.408)
(3086.461,5403.731)(3150.179,5408.113)(3215.837,5410.530)(3282.735,5410.963)
(3350.171,5409.390)(3417.446,5405.789)(3483.859,5400.138)(3548.709,5392.417)
(3611.295,5382.604)(3670.919,5370.677)(3726.877,5356.615)(3778.471,5340.396)
(3825.000,5322.000)
\path(3825,5322)(3872.594,5297.003)(3919.928,5268.538)(3967.330,5236.212)
(4015.132,5199.637)(4063.662,5158.420)(4113.251,5112.172)(4164.230,5060.501)
(4216.927,5003.017)(4271.674,4939.330)(4328.800,4869.049)(4358.358,4831.313)
(4388.635,4791.782)(4419.672,4750.407)(4451.510,4707.140)(4484.190,4661.931)
(4517.753,4614.731)(4552.242,4565.492)(4587.696,4514.165)(4624.158,4460.701)
(4661.668,4405.052)(4700.269,4347.168)(4740.000,4287.000)
\path(4543.528,4463.011)(4740.000,4287.000)(4656.339,4537.164)
\path(885,4332)(866.947,4293.245)(848.342,4249.161)(829.389,4200.472)
(810.295,4147.898)(791.265,4092.163)(772.504,4033.988)(754.220,3974.097)
(736.616,3913.211)(719.900,3852.053)(704.276,3791.345)(689.951,3731.810)
(677.130,3674.169)(666.018,3619.145)(656.822,3567.461)(649.748,3519.838)
(645.000,3477.000)
\path(645,3477)(640.060,3434.596)(634.463,3389.279)(628.335,3341.238)
(621.800,3290.658)(614.982,3237.727)(608.007,3182.631)(601.000,3125.557)
(594.084,3066.691)(587.385,3006.221)(581.027,2944.332)(575.136,2881.213)
(569.835,2817.049)(565.250,2752.027)(561.505,2686.334)(558.726,2620.157)
(557.036,2553.682)(556.561,2487.097)(557.425,2420.588)(559.753,2354.341)
(563.670,2288.544)(569.301,2223.382)(576.770,2159.044)(586.201,2095.715)
(597.720,2033.583)(611.452,1972.833)(627.521,1913.654)(646.052,1856.231)
(667.169,1800.751)(690.998,1747.402)(717.663,1696.369)(747.289,1647.839)
(780.000,1602.000)
\path(780,1602) (811.607,1562.074)(845.295,1522.689)(880.973,1483.936)
(918.550,1445.907)(957.934,1408.694)(999.033,1372.387)(1041.756,1337.079)
(1086.012,1302.862)(1131.709,1269.826)(1178.756,1238.064)(1227.060,1207.667)
(1276.531,1178.728)(1327.077,1151.336)(1378.607,1125.585)(1431.028,1101.566)
(1484.250,1079.370)(1538.181,1059.089)(1592.729,1040.815)(1647.804,1024.639)
(1703.313,1010.654)(1759.165,998.950)(1815.268,989.619)(1871.531,982.753)
(1927.863,978.443)(1984.171,976.782)(2040.366,977.861)(2096.354,981.771)
(2152.044,988.604)(2207.345,998.452)(2262.166,1011.406)(2316.415,1027.558)
(2370.000,1047.000)
\path(2370,1047)(2422.382,1070.080)(2472.351,1096.657)
(2519.971,1126.540)(2565.305,1159.533)(2608.416,1195.445)(2649.370,1234.082)
(2688.228,1275.251)(2725.055,1318.758)(2759.914,1364.411)(2792.869,1412.015)
(2823.984,1461.378)(2853.323,1512.306)(2880.948,1564.607)(2906.924,1618.086)
(2931.314,1672.551)(2954.182,1727.809)(2975.592,1783.665)(2995.607,1839.928)
(3014.291,1896.403)(3031.707,1952.898)(3047.919,2009.218)(3062.991,2065.172)
(3076.987,2120.565)(3089.969,2175.205)(3102.002,2228.898)(3113.150,2281.450)
(3123.475,2332.669)(3133.042,2382.362)(3141.915,2430.334)(3150.156,2476.394)
(3157.830,2520.347)(3165.000,2562.000)
\path(3165,2562)(3174.400,2626.518)(3183.746,2694.571)(3192.891,2765.912)
(3201.691,2840.295)(3205.915,2878.550)(3209.998,2917.473)(3213.921,2957.033)
(3217.666,2997.200)(3221.216,3037.942)(3224.551,3079.229)(3227.654,3121.030)
(3230.506,3163.314)(3233.089,3206.051)(3235.385,3249.208)(3237.375,3292.757)
(3239.042,3336.665)(3240.366,3380.902)(3241.331,3425.437)(3241.917,3470.240)
(3242.106,3515.279)(3241.881,3560.524)(3241.222,3605.944)(3240.112,3651.508)
(3238.533,3697.185)(3236.465,3742.945)(3233.891,3788.756)(3230.793,3834.588)
(3227.153,3880.410)(3222.951,3926.191)(3218.170,3971.901)(3212.792,4017.508)
(3206.799,4062.981)(3200.172,4108.291)(3192.892,4153.406)(3184.943,4198.295)
(3176.304,4242.927)(3166.960,4287.272)(3156.890,4331.299)(3146.076,4374.976)
(3134.502,4418.274)(3122.147,4461.161)(3108.995,4503.607)(3095.026,4545.580)
(3080.223,4587.051)(3064.567,4627.987)(3048.040,4668.358)(3030.624,4708.134)
(3012.301,4747.284)(2993.052,4785.776)(2972.859,4823.580)(2929.568,4897.001)
(2882.283,4967.301)(2830.857,5034.231)(2775.145,5097.546)(2715.000,5157.000)
\path(2715,5157)(2660.373,5202.668)(2600.381,5241.869)(2535.752,5274.844)
(2467.214,5301.835)(2395.496,5323.084)(2321.326,5338.833)(2283.549,5344.721)
(2245.432,5349.324)(2207.066,5352.673)(2168.543,5354.797)(2129.952,5355.729)
(2091.386,5355.496)(2052.936,5354.131)(2014.692,5351.662)(1976.745,5348.120)
(1939.187,5343.536)(1865.600,5331.361)(1794.659,5315.378)(1727.094,5295.829)
(1663.631,5272.956)(1605.000,5247.000)
\path(1605,5247)(1544.425,5218.274)(1485.328,5180.855)(1427.837,5135.793)
(1372.080,5084.137)(1318.186,5026.937)(1266.284,4965.243)(1216.500,4900.104)
(1168.965,4832.569)(1123.806,4763.688)(1081.151,4694.511)(1041.129,4626.087)
(1003.868,4559.466)(969.496,4495.697)(938.142,4435.830)(909.934,4380.915)
(885.000,4332.000)
\path(705,4872) (672.749,4800.190)(657.305,4757.519)(642.430,4711.243)
(628.212,4662.040)(614.737,4610.591)(602.093,4557.575)(590.366,4503.671)
(579.644,4449.559)(570.012,4395.917)(561.558,4343.426)(554.370,4292.764)
(548.532,4244.611)(544.134,4199.647)(541.261,4158.550)(540.000,4122.000)
\path(540,4122) (539.192,4076.851)(538.801,4026.413)(539.054,3971.450)
(540.180,3912.724)(542.409,3850.997)(545.967,3787.032)(551.084,3721.591)
(557.989,3655.436)(566.909,3589.330)(578.075,3524.036)(591.713,3460.315)
(608.053,3398.930)(627.323,3340.644)(649.752,3286.218)(675.568,3236.416)
(705.000,3192.000)
\path(705,3192) (752.389,3136.167)(808.502,3082.379)(872.283,3030.748)
(942.680,2981.387)(980.030,2957.593)(1018.640,2934.409)(1058.376,2911.848)
(1099.108,2889.924)(1140.703,2868.653)(1183.031,2848.047)(1225.959,2828.121)
(1269.356,2808.889)(1313.090,2790.364)(1357.030,2772.562)(1401.043,2755.496)
(1444.998,2739.180)(1488.763,2723.627)(1532.207,2708.853)(1575.198,2694.871)
(1617.604,2681.696)(1659.294,2669.340)(1700.136,2657.819)(1739.997,2647.147)
(1778.748,2637.336)(1852.387,2620.359)(1920.000,2607.000)
\path(1920,2607)(1964.482,2600.214)(2011.898,2594.465)(2062.050,2589.734)
(2114.738,2586.005)(2169.763,2583.259)(2226.924,2581.479)(2286.024,2580.648)
(2346.862,2580.749)(2409.238,2581.763)(2472.955,2583.673)(2537.811,2586.462)
(2603.608,2590.112)(2670.146,2594.606)(2737.227,2599.925)(2804.649,2606.054)
(2872.215,2612.974)(2939.724,2620.667)(3006.978,2629.117)(3073.776,2638.305)
(3139.920,2648.214)(3205.210,2658.827)(3269.446,2670.126)(3332.430,2682.093)
(3393.961,2694.712)(3453.840,2707.964)(3511.869,2721.833)(3567.847,2736.300)
(3621.575,2751.348)(3672.854,2766.959)(3721.484,2783.117)(3767.266,2799.803)
(3810.000,2817.000)
\path(3810,2817)(3881.606,2846.918)(3920.236,2863.106)(3960.508,2880.148)
(4002.238,2898.068)(4045.241,2916.893)(4089.336,2936.648)(4134.338,2957.358)
(4180.064,2979.048)(4226.332,3001.744)(4272.957,3025.472)(4319.756,3050.256)
(4366.546,3076.123)(4413.144,3103.097)(4459.366,3131.204)(4505.029,3160.470)
(4549.949,3190.919)(4593.944,3222.578)(4636.830,3255.471)(4678.423,3289.625)
(4718.540,3325.064)(4756.999,3361.813)(4793.615,3399.899)(4828.205,3439.347)
(4860.586,3480.182)(4890.575,3522.429)(4917.988,3566.115)(4942.642,3611.263)
(4964.353,3657.901)(4982.939,3706.053)(4998.216,3755.744)(5010.000,3807.000)
\path(5010,3807)(5019.278,3878.910)(5023.837,3950.781)(5023.861,4022.531)
(5019.538,4094.078)(5011.051,4165.339)(4998.585,4236.233)(4982.327,4306.678)
(4962.462,4376.592)(4939.174,4445.893)(4912.648,4514.499)(4883.071,4582.327)
(4850.627,4649.296)(4815.502,4715.324)(4777.880,4780.330)(4737.947,4844.230)
(4695.889,4906.943)(4651.890,4968.386)(4606.135,5028.479)(4558.811,5087.139)
(4510.102,5144.283)(4460.193,5199.831)(4409.270,5253.700)(4357.518,5305.807)
(4305.121,5356.072)(4252.267,5404.411)(4199.138,5450.744)(4145.922,5494.987)
(4092.802,5537.060)(4039.965,5576.879)(3987.596,5614.364)(3935.879,5649.431)
(3885.000,5682.000)
\path(3885,5682)(3846.170,5704.690)(3804.973,5725.570)(3761.573,5744.698)
(3716.133,5762.134)(3668.818,5777.936)(3619.789,5792.163)(3569.212,5804.875)
(3517.250,5816.129)(3464.066,5825.984)(3409.824,5834.500)(3354.688,5841.735)
(3298.821,5847.749)(3242.386,5852.599)(3185.549,5856.345)(3128.471,5859.045)
(3071.318,5860.759)(3014.251,5861.545)(2957.436,5861.462)(2901.035,5860.569)
(2845.212,5858.924)(2790.132,5856.587)(2735.956,5853.617)(2682.850,5850.071)
(2630.977,5846.010)(2580.499,5841.491)(2531.582,5836.574)(2484.388,5831.317)
(2439.082,5825.780)(2395.826,5820.021)(2354.785,5814.098)(2280.000,5802.000)
\path(2280,5802)(2218.461,5793.641)(2150.868,5781.237)(2078.188,5765.117)
(2040.242,5755.767)(2001.387,5745.610)(1961.743,5734.689)(1921.431,5723.045)
(1880.571,5710.718)(1839.286,5697.749)(1797.694,5684.181)(1755.918,5670.053)
(1714.078,5655.408)(1672.294,5640.285)(1630.687,5624.727)(1589.379,5608.773)
(1548.490,5592.467)(1508.140,5575.847)(1468.451,5558.957)(1429.543,5541.836)
(1354.554,5507.067)(1284.139,5471.871)(1219.264,5436.575)(1160.896,5401.508)
(1110.000,5367.000)
\path(1110,5367)(1059.229,5327.312)(1002.810,5274.511)(943.588,5211.984)
(884.408,5143.118)(828.114,5071.299)(777.551,4999.915)(735.565,4932.353)
(705.000,4872.000)
\path(4785,5457)(4743.024,5437.903)(4700.733,5415.814)(4658.194,5390.898)
(4615.473,5363.320)(4572.637,5333.246)(4529.751,5300.841)(4486.883,5266.270)
(4444.098,5229.700)(4401.464,5191.295)(4359.046,5151.220)(4316.910,5109.641)
(4275.125,5066.724)(4233.754,5022.634)(4192.866,4977.536)(4152.526,4931.596)
(4112.801,4884.979)(4073.758,4837.850)(4035.461,4790.375)(3997.979,4742.719)
(3961.378,4695.048)(3925.723,4647.527)(3891.081,4600.322)(3857.520,4553.597)
(3825.104,4507.518)(3793.900,4462.251)(3763.975,4417.961)(3735.396,4374.814)
(3708.228,4332.974)(3682.538,4292.607)(3658.392,4253.879)(3615.000,4182.000)
\path(3615,4182)(3591.526,4141.229)(3567.021,4097.430)(3541.611,4050.777)
(3515.425,4001.448)(3488.589,3949.617)(3461.233,3895.461)(3433.482,3839.154)
(3405.466,3780.874)(3377.311,3720.796)(3349.145,3659.095)(3321.096,3595.948)
(3293.290,3531.529)(3265.857,3466.016)(3238.924,3399.584)(3212.617,3332.407)
(3187.065,3264.664)(3162.395,3196.528)(3138.736,3128.176)(3116.214,3059.784)
(3094.956,2991.528)(3075.092,2923.582)(3056.748,2856.124)(3040.052,2789.328)
(3025.132,2723.371)(3012.114,2658.429)(3001.128,2594.676)(2992.299,2532.290)
(2985.757,2471.445)(2981.628,2412.318)(2980.041,2355.084)(2981.122,2299.920)
(2985.000,2247.000)
\path(2985,2247)(2988.282,2202.072)(2992.446,2155.206)(2997.543,2106.581)
(3003.625,2056.375)(3010.742,2004.767)(3018.944,1951.933)(3028.284,1898.053)
(3038.811,1843.305)(3050.576,1787.866)(3063.631,1731.915)(3078.026,1675.630)
(3093.812,1619.189)(3111.040,1562.771)(3129.761,1506.553)(3150.026,1450.714)
(3171.885,1395.431)(3195.390,1340.884)(3220.591,1287.249)(3247.539,1234.706)
(3276.285,1183.432)(3306.880,1133.605)(3339.375,1085.404)(3373.820,1039.007)
(3410.267,994.592)(3448.766,952.337)(3489.369,912.421)(3532.125,875.020)
(3577.087,840.315)(3624.304,808.482)(3673.828,779.699)(3725.710,754.146)
(3780.000,732.000)
\path(3780,732) (3817.843,719.142)(3855.825,707.625)(3893.933,697.426)
(3932.154,688.519)(3970.476,680.881)(4008.885,674.488)(4047.369,669.315)
(4085.913,665.337)(4124.506,662.531)(4163.134,660.873)(4201.784,660.337)
(4240.442,660.900)(4279.097,662.538)(4317.735,665.225)(4356.343,668.939)
(4394.908,673.654)(4433.417,679.347)(4471.857,685.992)(4510.214,693.567)
(4548.476,702.045)(4586.630,711.404)(4624.663,721.619)(4662.562,732.666)
(4700.313,744.520)(4737.904,757.157)(4775.322,770.553)(4849.585,799.524)
(4922.998,831.239)(4995.457,865.504)(5066.858,902.124)(5137.097,940.905)
(5206.069,981.653)(5273.670,1024.175)(5339.795,1068.274)(5404.341,1113.758)
(5467.204,1160.432)(5528.278,1208.101)(5587.460,1256.573)(5644.646,1305.651)
(5699.732,1355.143)(5752.612,1404.854)(5803.183,1454.589)(5851.341,1504.154)
(5896.982,1553.356)(5940.000,1602.000)
\path(5940,1602)(5979.083,1653.893)(6016.259,1709.315)(6051.560,1768.045)
(6085.019,1829.860)(6116.667,1894.539)(6146.538,1961.859)(6174.663,2031.599)
(6201.075,2103.536)(6225.807,2177.448)(6237.552,2215.076)(6248.889,2253.114)
(6259.822,2291.535)(6270.356,2330.311)(6280.493,2369.414)(6290.238,2408.817)
(6299.595,2448.492)(6308.569,2488.411)(6317.162,2528.546)(6325.380,2568.870)
(6333.226,2609.355)(6340.704,2649.973)(6347.819,2690.696)(6354.574,2731.496)
(6360.973,2772.347)(6367.021,2813.219)(6372.721,2854.086)(6378.078,2894.919)
(6383.095,2935.691)(6387.777,2976.374)(6392.127,3016.941)(6396.150,3057.363)
(6399.850,3097.613)(6403.231,3137.663)(6406.296,3177.485)(6409.050,3217.052)
(6411.497,3256.335)(6413.641,3295.307)(6415.485,3333.941)(6417.035,3372.209)
(6418.294,3410.082)(6419.266,3447.533)(6420.364,3521.058)(6420.364,3592.563)
(6419.296,3661.824)(6417.193,3728.620)(6414.088,3792.730)(6410.013,3853.930)
(6405.000,3912.000)
\path(6405,3912)(6395.410,3971.209)(6380.685,4036.068)(6361.315,4105.657)
(6337.791,4179.056)(6324.624,4216.896)(6310.603,4255.343)(6295.789,4294.283)
(6280.242,4333.600)(6264.025,4373.179)(6247.198,4412.905)(6229.823,4452.663)
(6211.961,4492.339)(6193.674,4531.816)(6175.023,4570.981)(6156.069,4609.717)
(6136.873,4647.910)(6098.002,4722.208)(6058.901,4792.952)(6020.059,4859.224)
(5981.969,4920.103)(5945.119,4974.668)(5910.000,5022.000)
\path(5910,5022)(5864.913,5075.398)(5808.014,5133.915)(5742.541,5194.596)
(5671.736,5254.485)(5598.839,5310.626)(5527.091,5360.062)(5459.731,5399.839)
(5400.000,5427.000)
\path(5400,5427)(5335.020,5447.306)(5298.348,5456.409)(5259.483,5464.663)
(5218.873,5471.957)(5176.967,5478.180)(5134.211,5483.220)(5091.052,5486.966)
(5047.939,5489.307)(5005.319,5490.132)(4963.639,5489.329)(4923.346,5486.787)
(4848.713,5476.040)(4785.000,5457.000)
\path(795,5682) (832.142,5709.920)(870.534,5736.761)(910.136,5762.542)
(950.907,5787.283)(992.809,5811.002)(1035.799,5833.718)(1079.840,5855.451)
(1124.889,5876.220)(1170.908,5896.043)(1217.855,5914.940)(1265.692,5932.929)
(1314.377,5950.029)(1363.871,5966.261)(1414.133,5981.642)(1465.123,5996.192)
(1516.802,6009.929)(1569.129,6022.873)(1622.063,6035.043)(1675.565,6046.458)
(1729.595,6057.136)(1784.113,6067.098)(1839.078,6076.361)(1894.450,6084.945)
(1950.189,6092.869)(2006.255,6100.152)(2062.608,6106.813)(2119.207,6112.871)
(2176.013,6118.345)(2232.986,6123.255)(2290.084,6127.618)(2347.269,6131.454)
(2404.500,6134.783)(2461.737,6137.622)(2518.939,6139.992)(2576.067,6141.911)
(2633.081,6143.398)(2689.939,6144.473)(2746.603,6145.154)(2803.032,6145.460)
(2859.186,6145.410)(2915.025,6145.024)(2970.508,6144.321)(3025.596,6143.318)
(3080.248,6142.037)(3134.425,6140.494)(3188.085,6138.711)(3241.190,6136.704)
(3293.698,6134.495)(3345.570,6132.101)(3396.766,6129.541)(3447.245,6126.835)
(3496.967,6124.002)(3545.892,6121.061)(3593.981,6118.030)(3641.192,6114.929)
(3687.486,6111.777)(3732.822,6108.593)(3777.162,6105.396)(3820.463,6102.204)
(3862.686,6099.037)(3903.792,6095.915)(3943.740,6092.855)(3982.489,6089.877)
(4020.000,6087.000)
\path(4020,6087)(4078.255,6080.527)(4140.350,6073.675)(4206.015,6066.367)
(4274.981,6058.525)(4346.978,6050.071)(4421.735,6040.928)(4460.064,6036.074)
(4498.983,6031.018)(4538.456,6025.752)(4578.451,6020.264)(4618.934,6014.546)
(4659.871,6008.588)(4701.227,6002.379)(4742.971,5995.911)(4785.067,5989.174)
(4827.481,5982.158)(4870.182,5974.853)(4913.133,5967.249)(4956.302,5959.337)
(4999.656,5951.108)(5043.159,5942.551)(5086.779,5933.656)(5130.482,5924.415)
(5174.233,5914.817)(5218.000,5904.853)(5261.749,5894.512)(5305.445,5883.786)
(5349.055,5872.665)(5392.546,5861.138)(5435.883,5849.196)(5479.032,5836.830)
(5521.961,5824.030)(5564.635,5810.785)(5607.021,5797.087)(5649.084,5782.925)
(5690.792,5768.291)(5732.109,5753.173)(5773.004,5737.563)(5813.441,5721.451)
(5853.387,5704.827)(5892.809,5687.682)(5931.672,5670.005)(5969.943,5651.787)
(6007.588,5633.018)(6080.865,5593.790)(6151.234,5552.243)(6218.424,5508.298)
(6282.166,5461.879)(6342.189,5412.909)(6398.224,5361.308)(6450.000,5307.000)
\path(6450,5307)(6500.111,5243.271)(6547.270,5175.551)(6591.535,5104.093)
(6632.967,5029.152)(6652.639,4990.454)(6671.625,4950.980)(6689.932,4910.762)
(6707.569,4869.832)(6724.542,4828.221)(6740.859,4785.962)(6756.527,4743.085)
(6771.554,4699.623)(6785.947,4655.607)(6799.714,4611.070)(6812.862,4566.042)
(6825.398,4520.555)(6837.331,4474.643)(6848.667,4428.335)(6859.414,4381.663)
(6869.580,4334.661)(6879.172,4287.358)(6888.197,4239.788)(6896.663,4191.981)
(6904.577,4143.969)(6911.947,4095.785)(6918.780,4047.460)(6925.084,3999.025)
(6930.866,3950.513)(6936.134,3901.954)(6940.895,3853.382)(6945.156,3804.827)
(6948.925,3756.321)(6952.210,3707.896)(6955.018,3659.584)(6957.356,3611.417)
(6959.232,3563.425)(6960.653,3515.642)(6961.627,3468.098)(6962.161,3420.826)
(6962.263,3373.857)(6961.940,3327.222)(6961.199,3280.955)(6960.049,3235.085)
(6958.496,3189.646)(6956.548,3144.668)(6954.212,3100.184)(6951.497,3056.226)
(6948.409,3012.824)(6944.955,2970.011)(6941.144,2927.819)(6936.983,2886.278)
(6932.479,2845.422)(6927.639,2805.281)(6922.472,2765.888)(6916.984,2727.274)
(6911.183,2689.470)(6898.673,2616.423)(6885.000,2547.000)
\path(6885,2547)(6871.541,2487.955)(6855.610,2426.694)(6837.281,2363.419)
(6816.629,2298.335)(6793.727,2231.645)(6768.649,2163.552)(6741.468,2094.259)
(6712.260,2023.971)(6681.097,1952.889)(6648.054,1881.219)(6613.205,1809.162)
(6576.623,1736.923)(6538.383,1664.704)(6498.558,1592.710)(6457.222,1521.143)
(6414.450,1450.207)(6370.315,1380.106)(6324.890,1311.042)(6278.251,1243.220)
(6230.470,1176.841)(6181.623,1112.111)(6131.781,1049.232)(6081.021,988.407)
(6029.415,929.841)(5977.037,873.735)(5923.962,820.295)(5870.263,769.722)
(5816.015,722.221)(5761.290,677.995)(5706.163,637.247)(5650.709,600.181)
(5595.000,567.000)
\path(5595,567) (5544.970,539.081)(5493.556,511.901)(5440.799,485.464)
(5386.745,459.773)(5331.436,434.831)(5274.916,410.642)(5217.228,387.207)
(5158.415,364.531)(5098.522,342.617)(5037.590,321.468)(4975.665,301.086)
(4912.789,281.476)(4849.005,262.639)(4784.358,244.580)(4718.890,227.301)
(4652.645,210.806)(4585.666,195.098)(4517.998,180.179)(4449.682,166.054)
(4380.763,152.724)(4311.283,140.194)(4241.288,128.466)(4170.819,117.544)
(4099.920,107.430)(4028.635,98.129)(3957.007,89.642)(3885.079,81.973)
(3812.896,75.125)(3740.499,69.102)(3667.934,63.906)(3595.243,59.541)
(3522.469,56.010)(3449.656,53.316)(3376.848,51.461)(3304.087,50.450)
(3231.418,50.285)(3158.883,50.969)(3086.527,52.506)(3014.392,54.899)
(2942.522,58.151)(2870.960,62.264)(2799.750,67.243)(2728.935,73.090)
(2658.559,79.808)(2588.664,87.401)(2519.296,95.872)(2450.496,105.223)
(2382.308,115.459)(2314.776,126.581)(2247.943,138.594)(2181.853,151.500)
(2116.548,165.302)(2052.073,180.004)(1988.470,195.609)(1925.784,212.120)
(1864.058,229.540)(1803.334,247.872)(1743.657,267.119)(1685.069,287.285)
(1627.615,308.372)(1571.338,330.384)(1516.281,353.324)(1462.487,377.195)
(1410.000,402.000)
\path(1410,402) (1366.305,425.145)(1323.000,451.582)(1280.118,481.125)
(1237.694,513.591)(1195.763,548.793)(1154.357,586.547)(1113.513,626.667)
(1073.264,668.968)(1033.644,713.264)(994.687,759.372)(956.429,807.105)
(918.903,856.278)(882.144,906.706)(846.186,958.204)(811.062,1010.587)
(776.809,1063.669)(743.459,1117.265)(711.047,1171.191)(679.608,1225.260)
(649.176,1279.289)(619.784,1333.091)(591.468,1386.481)(564.262,1439.274)
(538.200,1491.285)(513.315,1542.330)(489.644,1592.221)(467.219,1640.775)
(446.076,1687.807)(426.248,1733.130)(407.770,1776.560)(390.676,1817.912)
(375.000,1857.000)
\path(375,1857) (357.740,1897.112)(340.490,1940.278)
(323.296,1986.305)(306.199,2035.000)(289.244,2086.172)
(272.475,2139.629)(255.936,2195.178)(239.670,2252.627)(223.721,2311.785)
(208.132,2372.459)(192.949,2434.457)(178.213,2497.586)(163.969,2561.656)
(150.261,2626.473)(137.133,2691.845)(124.628,2757.581)(112.789,2823.488)
(101.662,2889.375)(91.289,2955.048)(81.714,3020.316)(72.981,3084.987)
(65.134,3148.868)(58.216,3211.768)(52.271,3273.495)(47.344,3333.855)
(43.477,3392.658)(40.714,3449.711)(39.100,3504.821)(38.678,3557.798)
(39.491,3608.448)(41.584,3656.579)(45.000,3702.000)
\path(45,3702)  (49.990,3751.580)(55.833,3804.135)(62.562,3859.445)
(70.211,3917.292)(78.814,3977.460)(88.405,4039.729)(99.018,4103.882)
(110.685,4169.700)(123.441,4236.966)(137.320,4305.461)(152.356,4374.968)
(168.581,4445.267)(186.031,4516.142)(204.738,4587.374)(224.736,4658.745)
(246.060,4730.036)(268.743,4801.031)(292.818,4871.510)(318.319,4941.256)
(345.281,5010.051)(373.737,5077.676)(403.720,5143.913)
(435.265,5208.546)(468.405,5271.354)(503.174,5332.121)
(539.605,5390.627)(577.733,5446.656)(617.591,5499.989)
(659.213,5550.408)(702.633,5597.695)(747.884,5641.632)(795.000,5682.000)
\put(7590,3987){\shade\ellipse{210}{210}}
\put(7590,3987){\ellipse{210}{210}}
\path(7725.000,5599.500)(7470.000,5532.000)(7725.000,5464.500)
\dottedline{67}(7470,5532)(8565,5532)
\path(8310.000,5464.500)(8565.000,5532.000)(8310.000,5599.500)
\path(7709.090,4852.849)(7455.000,4782.000)(7710.866,4717.861)
\dashline{90.000}(7455,4782)(8595,4797)
\path(8340.910,4726.151)(8595.000,4797.000)(8339.134,4861.139)
\path(7485,3267)(7537.569,3323.931)(7602.809,3363.532)(7677.053,3388.745)
(7716.406,3396.876)(7756.635,3402.514)(7797.281,3406.026)(7837.887,3407.781)
(7877.994,3408.145)(7917.143,3407.489)(7990.737,3404.581)(8055.000,3402.000)
\path(8055,3402)(8128.875,3393.256)(8171.155,3388.312)(8216.050,3382.471)
(8262.849,3375.348)(8310.841,3366.557)(8359.315,3355.712)(8407.560,3342.427)
(8454.866,3326.317)(8500.522,3306.994)(8543.817,3284.074)(8584.040,3257.170)
(8652.428,3189.868)(8679.171,3148.698)(8700.000,3102.000)
\path(8700,3102)(8714.986,3046.267)(8713.130,2990.717)(8697.766,2936.257)
(8672.227,2883.791)(8639.848,2834.227)(8603.962,2788.470)(8567.901,2747.425)
(8535.000,2712.000)
\path(8535,2712)(8490.187,2680.283)(8435.525,2649.765)(8374.036,2621.430)
(8308.744,2596.264)(8242.671,2575.252)(8178.840,2559.381)(8120.276,2549.635)
(8070.000,2547.000)
\path(8070,2547)(8017.887,2549.849)(7960.697,2558.411)(7900.913,2572.102)
(7841.017,2590.335)(7783.495,2612.527)(7730.829,2638.091)(7685.503,2666.444)
(7650.000,2697.000)
\path(7650,2697)(7606.035,2751.123)(7561.930,2813.579)(7521.091,2882.647)
(7486.920,2956.609)(7473.399,2994.887)(7462.822,3033.744)(7455.613,3072.965)
(7452.200,3112.335)(7453.006,3151.638)(7458.458,3190.660)(7468.981,3229.185)
(7485.000,3267.000)
%
\put(9135,5472){\makebox(0,0)[lb]{\smash{chosen route}}}
\put(9180,4737){\makebox(0,0)[lb]{\smash{shortest route}}}
\put(9240,3927){\makebox(0,0)[lb]{\smash{pivot}}}
\put(9240,3012){\makebox(0,0)[lb]{\smash{cluster}}}
%
\end{picture}
}}
%
\afigcap{5}{\protect\textsupscript{VPL}{m-m} on a general graph}
%
\end{figure*}
%
\apar{5.1-4}
We now present a precise definition of the above scheme\@.
These definitions are based on~\cite{cj96-04-02}\@.
%
\begin{alabsubtext}{Definition}{11}{}
%
The \emph{\(j\)-neighborhood} of a node \(v\in V\) is defined as
%
\[\neighborhood _{j}(v)=\setof{w}{d_{G}(v,w)\leq j}\]
\sentence
%
The \emph{radius} of a node wrt a graph is defined by
\[\radius(v,G)=\max_{w\in V}d_G(v,w)\]
\sentence
%
The \emph{radius} of a graph is defined by
%
\[\radius(G)=\min_{v\in V}\radius(v,G)\]
\sentence
%
A \emph{center} of a graph is a node for which
\(\radius(v,G)=\radius(G)\)\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Definition}{12}{}
%
Given a set of nodes \(C\subseteq V\), let \(G(C)\) denote the subgraph
induced by \(C\) in \(G\)\@. A \emph{cluster} is a subset \(C\) of nodes such
that \(G(C)\) is connected\@. We use \(\radius(v,C)\) as a shorthand for
\(\radius(v,G(C))\)\@. A \emph{cover} is a collection of clusters
\(\setofclust{C}=\setof{C_{i}}{1\leq i\leq\delta}\) such that
\(\unionset_{i}C_{i}=V\)\@. Extend the definitions of radius by
\(\radius(\setofclust{C})=\max_{i}\radius(C_i)\)\@. For a node \(v\) let
\(\Delta(\setofclust{C},v)\) denote the number of occurrences of \(v\)
in the clusters \(C_{i}\)\@. The \emph{maximum degree} of a cover
\(\setofclust{C}\) is defined as
\(\Delta(\setofclust{C})=\max_{v\in V}\Delta(\setofclust{C},v)\)\@.
Given two covers
\(\setofclust{C}=\setof{C_{i}}{1\leq i\leq\delta}\) and
\(\setofclust{T}=\setof{T_{i}}{1\leq i\leq k}\) we say that
\(\setofclust{T}\) \emph{subsumes} \(\setofclust{C}\) if for every
\(C_{i}\in\setofclust{C}\) there exists a \(T_{j}\in\setofclust{T}\)
such that \(C_{i}\subseteq T_{j}\)\@.
%
\end{alabsubtext}
%
\apar{5.1-5}
We rely on the following theorem: 
%
\begin{alabsubtext}{Theorem}{2}{\cite{cj96-04-02}}
%
Given a graph \(G\), a cover \(\setofclust{C}\), and an integer
\(k\geq 1\), it is possible to construct a cover \(\setofclust{T}\)
that satisfies the following properties:
%
\begin{enumerate}
%
\item[1.] \(\setofclust{T}\) subsumes \(\setofclust{C}\),
%
\item[2.] \(\radius(\setofclust{T})\leq(2k-1)\radius(\setofclust{C})\), and
%
\item[3.] \(\Delta(\setofclust{T})=
\orderof{k\setsize{\setofclust{C}}^{1/k}}\)\@.
%
\end{enumerate}
%
\end{alabsubtext}
\sentence
%
Intuitively, this theorem states that the graph can be divided 
into overlapping clusters, with three important properties:
%
\begin{enumerate}
%
\item[1.] For each node \(v\) there is a cluster that includes \(v\),
and all its \(\delta\)-neighborhood (recall that \(\delta\) is a
parameter of the algorithm)\@.
%
\item[2.] The distance between every pair of nodes in each cluster is not
more than \((2k-1)\delta\)\@.
%
\item[3.] Each node is included in not-too-many clusters (i.e.,
\(\orderof{kN^{1/k}}\))\@.
%
\end{enumerate}
%
\apar{5.1-6}
Our construction is based on the routing scheme from \cite{cj96-04-02}, 
combined with the usage of \textsupscript{VPL}{1-m} for trees\@.
We first present a scheme that depends on a parameter \(\delta\), 
and then tune the scheme by choosing \(\delta\)\@.
The scheme connects pairs of nodes with a distance not
exceeding~\(\delta\)\@.
%
\begin{algorithm}{informal}{}
%
\item[0.] \kwd{function}
\(\progfunc{\idr{general\_vpl}}(G\oftype\text{network},\; 
\delta,k\oftype\universe{N})\) \comment{\(\delta,k>0\)}
%
\item[1.] \progind\kwd{returns} \textsupscript{VPL}{m-m}
%
\item[2.] \progind
\(\setofclust{C}\assigned\setof{\neighborhood_{\delta}(v)}{v\in V(G)}\)
%
\item[3.] \progind Construct \(\setofclust{T}\) as in Theorem~2
%
\item[4.] \progind Select a center \(c\) in each \(T_{i}\)
%
\item[5.] \progind Construct a \textsupscript{VPL}{1-m} in each \(T_{i}\) to
the center with \(h'=\frac{h}{2}\)
%
\item[6.] \progind \kwd{return} the union of all the above
\textsupscript{VPL}{1-m}s
%
\item[7.] \kwd{end function} \(\progfunc{\idr{general\_vpl}}\)
%
\end{algorithm}
%
\begin{alabsubtext}{Lemma}{8}{}
%
Let \(v,w\) be a pair of nodes such that \(d_G(v,w)\leq\delta\) and let
the stretch factor be \(\mu=8k\)\@. Then the number of hops between
\(v\) and \(w\) is \(\hopcount_{\mu}(v,w)\leq h\) in the
\textsupscript{VPL}{m-m} produced by algorithm
\algo{informal}{}{\(\progfunc{general\_vpl}\)}\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{8}{}
\prooffontshape
%
\apar{Proof of Lemma 8-1}
Clearly, \(v\in\neighborhood_{\delta}(w)\), and there exists a cluster
\(T_{i}\in\setofclust{T}\) that includes
\(\neighborhood_{\delta}(w)\)\@. The route chosen for \(v,w\) will use
the \textsupscript{VPL}{1-m} in \(T_i\) by going from \(v\) to the
root of the \textsupscript{VPL}{1-m} (using a shortest route) and from
there to \(w\); denote the total length of it by \(X\)\@. This route is
composed of no more than \(h\) VPs\@. Note that the distance to the
center in \(\neighborhood_{\delta}(w)\) is no more than \(\delta\),
and by Property~\(2\) of \(\setofclust{T}\) we have:
%
\[X\leq 2\radius(\setofclust{T})\leq
2(2k-1)\radius(\setofclust{C})=2(2k-1)\delta<4k\delta\]
\sentence
%
\apar{Proof of Lemma 8-2}
Now suppose that \(d_G(v,w)\geq\frac{\delta}{2}\),
then the stretch factor satisfies \(\mu\leq{\frac{4k\delta}{\delta/2}=8k}\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 8}}
\end{alabsubtext}
%
\begin{alabsubtext}{Lemma}{9}{}
%
Let \(\Psi\) be the \textsupscript{VPL}{m-m} produced by algorithm
\algo{informal}{}{\(\progfunc{general\_vpl}\)}\@. Then, its maximum load
satisfies
%
\[\loadonnode(\Psi)=\orderof{k h N^{\frac{1}{k}+\frac{2}{h}}}\]
\sentence
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{9}{}
\prooffontshape
%
\apar{Proof of Lemma 9-1}
By Theorem~2, each node is shared by at most
\(\Delta(\setofclust{T})=\orderof{k\setsize{\setofclust{C}}^{1/k}}\)
clusters\@. On the other hand, using Lemma~7, the load on a node caused
by a single \textsupscript{VPL}{1-m} is
\(\loadonnode(\Psi^{1-m})\leq\frac{h}{2} N^{2/h}\), and since
\(\setsize{\setofclust{C}}\leq N\) we get
%
\[\loadonnode(\Psi)=
\orderof{h N^{\frac{2}{h}} k N^{\frac{1}{k}}}=
\orderof{k h N^{\frac{1}{k}+\frac{2}{h}}}\]
\sentence
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 9}}
\end{alabsubtext}
%
\apar{Proof of Lemma 9-2}
So far, we have assumed that the distance between \(v\) and \(w\) is
not less than \(\frac{\delta}{2}\)\@. To achieve this, we apply the
entire scheme for increasing values of \(\delta\)\@. We start with
\(\delta=2\) and at the \(i\)th round take \(\delta=2^{i}\)\@. Clearly,
this process completes in \(\log_{2}N\) rounds\@. To ensure that the
assumption used for the calculation of the stretch factor holds, we
choose the \textsupscript{VPL}{1-m} to connect \(v\) and \(w\) in the
smallest cluster that includes both nodes\@. If we take \(\delta=2^{i}\)
for an \(i\) that satisfies \(2^{i-1}\leq d(v,w)\leq 2^{i}\), then we
have \(\frac{\delta}{2}\leq d(v,w)\) as assumed earlier\@. This process
multiplies the load by a factor of \(\log_{2}N\), so we have
%
\[\loadonnode(\Psi)=
\orderof{k h\log N N^{\frac{1}{k}+\frac{2}{h}}}\]
\sentence
%
The following theorem summarizes the characteristics of the above
description:
%
\begin{alabsubtext}{Theorem}{3}{}
%
Given an arbitrary network \(G\) with \(N\) nodes, and \(k,h>1\), the above
scheme yields an \(h\)-feasible \textsupscript{VPL}{m-m} with stretch
factor \(\mu\leq 8k\) and load
\(\loadonnode(\Psi)=
\orderof{k h\log N N^{\frac{1}{k}+\frac{2}{h}}}\)\@.
%
\end{alabsubtext}
\sentence
%
\asection{6}{Summary}
%
\apar{6-1}
In this paper we presented a model and a class of problems for
designing the layout of virtual paths in a given ATM network to be
used for general-purpose connection routing\@. We first defined the
characteristics that are important for such a layout, the
\textsupscript{VPL}{m-m} problem, and the simpler
\textsupscript{VPL}{1-m} problem\@. Next, we showed that both problems
are NP-complete, but presented an optimal construction scheme for a
more limited variant of the \textsupscript{VPL}{1-m} (namely, with
stretch factor \(\mu=1\) and assuming a tree network)\@. We then
demonstrated how this limited problem can serve as a building block
for a suboptimal solution of a \textsupscript{VPL}{m-m} (in which
\(\mu>1\))\@.
%
\apar{6-2}
We believe that our approach quite accurately models certain routing
problems in ATM networks, including the optimality criterion\@. We
expect this work to motivate further work in finding better schemes
for general networks, in extending the existing schemes for supporting
fault tolerance in the network, and in extending the characteristics
of a good layout to the case when some statistics regarding the volume
and bandwidth of connections between every pair of nodes is known\@.
%
\asection{7}{Acknowledgment}
%
We would like to thank the managing editor of this journal, Mike
O'Donnell, and the copy editor, Lisa Clark, for their very thorough
and involved work in improving the presentation of this paper\@.
%
\asection{A}{Appendix}
%
\asubsection{A.1}{NP-Completeness Result for the
\protect\textsupscript{VPL}{1-m} Problem}
%
\apar{A.1-1}
Recalling the problem statement in Section~4, we now prove that the
OPT-\textsupscript{VPL}{1-m} problem is NP-complete (if the stretch
factor is unbounded)\@.
%
\begin{alabsubtext}{Theorem}{4}{}
%
OPT-\textsupscript{VPL}{1-m} is NP-complete\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{4}{}
\prooffontshape
%
\apar{Proof of Theorem 4-1}
{\sloppy
Clearly OPT-\textsupscript{VPL}{1-m} is in NP\@.
To show NP-completeness, we reduce it~to:
%
\begin{description}
%
\item[\problemlabel{Problem:}] The disjoint connecting paths problem (ND40)
\cite{cj96-04-14}.
%
\item[\problemlabel{Instance:}] An undirected graph \(G=(V,E)\), collection of
disjoint pairs of nodes \((s_{1},t_{1}),(s_{2},t_{2}),\dots,\)
\((s_{k},t_{k})\).
%
\item[\problemlabel{Question:}] Does \(G\) contain \(k\) mutually node-disjoint
paths, one connecting \(s_{i}\) and \(t_{i}\) for each
\(i\in\{1,\dots,k\}\)\@?
%
\end{description}
}
%
Given an instance of ND40, let \(n=\setsize{V}\)\@. Define the following
components (see Figure~6):
%
\begin{description}
%
\item[Extender (\(\extender_{p}(v,w)\)):]
This component \emph{extends} a path that goes through \(v\) and \(w\) in
\(V\) to include \(p\) additional hops\@. It is composed of a path of \(p\)
nodes \(a_{1},\dots,a_{p}\), each of which is connected to \(n-2\) new nodes
\(b^{a_{i}}_{1},\dots,b^{a_{i}}_{n-2}\)\@. In addition, \(v\) is connected to
\(a_{1}\) and \(w\) to \(a_{p}\)\@. In the case when \(p=0\), the
extender reduces to an edge \((v,w)\)\@.
%
\item[Limiter (\(\limiter_{p}(v)\)):]
This component \emph{limits} the path from its head \(v\) to the root,
to include no more than \(h-p\) hops\@. It also limits the number of VPs
that may go through \(v\)\@. The limiter is constructed by connecting
\(n-3\) new nodes (\(b^{v}_{1},\dots,b^{v}_{n-3}\)) to \(v\), adding
yet another new node \(c_{v}\), and connecting \(v\) and \(c_v\) by
\(\extender_{p-1}(v,c_{v})\)\@.
%
\end{description}
%
\begin{figure*}
%
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.0052ex}
%
\begin{picture}(14464,5891)(0,-10)
\thicklines
%
\put(1500,3700){\makebox(0,0)[lb]{{\Huge\(=\)}}}
%
\path(12,4443)(972,4443)(972,2433)
(12,2433)(12,4443)
\put(4392,1638){\ellipse{120}{120}}
\put(4392,1878){\ellipse{120}{120}}
\put(4392,2103){\ellipse{120}{120}}
\put(4392,2328){\ellipse{120}{120}}
\path(4332,1638)(3822,1818)
\path(4332,1878)(3867,1893)
\path(4347,2328)(3852,2088)
\path(4332,2088)(3882,1998)
\put(4392,4488){\ellipse{120}{120}}
\put(4392,4728){\ellipse{120}{120}}
\put(4392,4953){\ellipse{120}{120}}
\put(4392,5178){\ellipse{120}{120}}
\path(4332,4488)(3822,4668)
\path(4332,4728)(3867,4743)
\path(4347,5178)(3852,4938)
\path(4332,4938)(3882,4848)
%
\put(8600,4000){\makebox(0,0)[lb]{{\Huge\(=\)}}}
%
\put(11607,3648){\ellipse{120}{120}}
\put(11877,3663){\ellipse{120}{120}}
\put(12132,3663){\ellipse{120}{120}}
\texture{%
cccccccc 0 0 0 cccccccc 0 0 0 
cccccccc 0 0 0 cccccccc 0 0 0 
cccccccc 0 0 0 cccccccc 0 0 0 
cccccccc 0 0 0 cccccccc 0 0 0
}%
\put(7542,4758){\shade\ellipse{210}{210}}
\put(7542,4758){\ellipse{210}{210}}
\put(10992,5763){\shade\ellipse{210}{210}}
\put(10992,5763){\ellipse{210}{210}}
\put(10692,1698){\ellipse{120}{120}}
\path(7467,4713)(6867,3288)(8217,3288)(7617,4713)
\path(12117,3738)(11067,5688)
\path(11817,3738)(11067,5688)
\path(11592,3663)(11067,5688)
\path(10992,5688)(10617,4188)
\dottedline{67}(10917,5763)(8517,1488)(14442,1488)(11067,5688)
\path(10692,2238)(10692,1788)
\path(10137,4218)(11097,4218)(11097,2208)(10137,2208)(10137,4218)
\put(7332,5028){\makebox(0,0)[lb]{\smash{\(\scriptstyle v\)}}}
\put(10917,1638){\makebox(0,0)[lb]{\smash{\(\scriptstyle c_{v}\)}}}
\put(10542,5748){\makebox(0,0)[lb]{\smash{\(\scriptstyle v\)}}}
\put(9237,33){\makebox(0,0)[lb]{\smash{A limiter \(\limiter_{p}(v)\)}}}
\put(7377,3738){\makebox(0,0)[lb]{\smash{\(\scriptstyle p\)}}}
\put(10272,3138){\makebox(0,0)[lb]{\smash{\(\scriptstyle p-1\)}}}
\put(11517,3138){\makebox(0,0)[lb]{\smash{\(\scriptstyle b^{v}_{1}\ldots b^{v}_{n-3}\)}}}
\put(4362,2868){\ellipse{120}{120}}
\put(4362,3108){\ellipse{120}{120}}
\put(4362,3333){\ellipse{120}{120}}
\put(4362,3558){\ellipse{120}{120}}
\path(4302,2868)(3792,3048)
\path(4302,3108)(3837,3123)
\path(4317,3558)(3822,3318)
\path(4302,3318)(3852,3228)
\put(3642,5763){\shade\ellipse{210}{210}}
\put(3642,5763){\ellipse{210}{210}}
\put(3642,963){\shade\ellipse{210}{210}}
\put(3642,963){\ellipse{210}{210}}
\put(432,4848){\shade\ellipse{180}{180}}
\put(432,4848){\ellipse{180}{180}}
\put(432,2028){\shade\ellipse{180}{180}}
\put(432,2028){\ellipse{180}{180}}
\put(3612,1953){\ellipse{540}{540}}
\put(3642,4788){\ellipse{540}{540}}
\put(3642,4098){\blacken\ellipse{90}{90}}
\put(3642,4098){\ellipse{90}{90}}
\put(3642,4248){\blacken\ellipse{90}{90}}
\put(3642,4248){\ellipse{90}{90}}
\put(3642,3933){\blacken\ellipse{90}{90}}
\put(3642,3933){\ellipse{90}{90}}
\put(3582,3183){\ellipse{540}{540}}
\path(3642,5688)(3642,5088)
\path(3642,1713)(3642,1038)
\path(417,4788)(417,4413)
\path(417,2463)(417,2088)
\dottedline{67}(2892,5463)(5217,5463)(5217,1413)(2892,1413)(2892,5463)
\path(3642,4488)(3642,4368)
\path(3627,3453)(3642,3813)
\path(3612,2943)(3612,2223)
\put(3492,1878){\makebox(0,0)[lb]{\smash{\(\scriptstyle a_{1}\)}}}
\put(3492,4713){\makebox(0,0)[lb]{\smash{\(\scriptstyle a_{p}\)}}}
\put(342,3363){\makebox(0,0)[lb]{\smash{\(\scriptstyle p\)}}}
\put(342,1548){\makebox(0,0)[lb]{\smash{\(\scriptstyle v\)}}}
\put(342,5073){\makebox(0,0)[lb]{\smash{\(\scriptstyle w\)}}}
\put(3147,873){\makebox(0,0)[lb]{\smash{\(\scriptstyle v\)}}}
\put(3087,5688){\makebox(0,0)[lb]{\smash{\(\scriptstyle w\)}}}
\put(4542,1578){\makebox(0,0)[lb]{\smash{\(\scriptstyle b_{1}^{a_{1}}\)}}}
\put(4542,2253){\makebox(0,0)[lb]{\smash{\(\scriptstyle b_{n-2}^{a_{1}}\)}}}
\put(4467,5103){\makebox(0,0)[lb]{\smash{\(\scriptstyle b_{n-2}^{a_{p}}\)}}}
\put(1077,33){\makebox(0,0)[lb]{\smash{An extender \(\extender_p(v,w)\)}}}
\put(4467,4428){\makebox(0,0)[lb]{\smash{\(\scriptstyle b_{1}^{a_{p}}\)}}}
\put(3462,3093){\makebox(0,0)[lb]{\smash{\(\scriptstyle a_{2}\)}}}
\put(4512,2808){\makebox(0,0)[lb]{\smash{\(\scriptstyle b_{1}^{a_{2}}\)}}}
\put(4512,3483){\makebox(0,0)[lb]{\smash{\(\scriptstyle b_{n-2}^{a_{2}}\)}}}
%
\end{picture}
}}
%
\afigcap{6}{The limiter and extender components}
%
\end{figure*}
%
Let \(U=V\setminus\{t_1,t_2,\dots,t_k\}\), let \(L=n\), and \(h=k+2\)\@.
Consider the following transformation of \(G\) to \(G'\) (see
Figure~7, in which the extender is drawn as a rectangle and the
limiter as a triangle):
%
\begin{itemize}
%
\item Initially define \(G'\) as \(G\)\@.
%
\item Add a new node \(r\) to \(G'\)\@.
%
\item Add a limiter \(\limiter_{1}(v)\) to every node \(v\in U\)\@.
%
\item Add an extender \(\extender_{h-1}(v,r)\) for every node \(v\in U\)\@.
%
\item Add an extender \(\extender_{h-i+1}(s_{i},r)\) to every
\(s_i,i\in\{1,\dots,k\}\)\@.
%
\item Add a limiter \(\limiter_{i}(t_i)\) to every
\(t_{i},i\in\{1,\dots,k\}\)\@.
%
\item Add a node \(d_{i}\) and an edge \((d_{i},t_{i})\) to every
\(t_{i},i\in\{1,\dots,k\}\)\@.
%
\end{itemize}
%
\begin{figure*}
%
\fbox{\parbox[t]{\textwidth}{%
\setlength{\unitlength}{0.007ex}
%
\begin{center}
%
\begin{picture}(10504,8751)(0,-10)
%
\put(7002,5577){\blacken\ellipse{150}{150}}
\put(7287,5577){\blacken\ellipse{150}{150}}
\put(7587,5577){\blacken\ellipse{150}{150}}
\put(6927,627){\blacken\ellipse{150}{150}}
\put(7212,627){\blacken\ellipse{150}{150}}
\put(7512,627){\blacken\ellipse{150}{150}}
\texture{%
aa555555 55bbbbbb bb555555 55fefefe fe555555 55bbbbbb bb555555 55eeefee 
ef555555 55bbbbbb bb555555 55fefefe fe555555 55bbbbbb bb555555 55efefef 
ef555555 55bbbbbb bb555555 55fefefe fe555555 55bbbbbb bb555555 55eeefee 
ef555555 55bbbbbb bb555555 55fefefe fe555555 55bbbbbb bb555555 55efefef
}
\put(4572,8292){\shade\ellipse{600}{600}}
\put(9657,5562){\ellipse{600}{600}}
\put(5442,5532){\ellipse{600}{600}}
\put(2232,2997){\ellipse{600}{600}}
\put(2412,1062){\ellipse{600}{600}}
\put(1212,1137){\ellipse{300}{300}}
\put(5412,1062){\ellipse{600}{600}}
\put(4212,1137){\ellipse{300}{300}}
\put(9462,1137){\ellipse{600}{600}}
\put(8262,1212){\ellipse{300}{300}}
\put(2067,5637){\ellipse{600}{600}}
\path(237,4512)(837,4587)(582,6027)(12,5937)(237,4512)
\path(3762,7662)(4362,8112)
\path(9612,5862)(8862,6612)
\path(7887,7587)(4857,8337)
\path(9402,5667)(8502,6192)(8427,4767)(9402,5367)
\path(10197,6432)(9777,6252)(9402,7257)(9807,7422)(10197,6432)
\path(4317,6492)(4767,6537)(4587,7617)(4167,7542)(4317,6492)
\path(5652,5682)(6552,6207)(6627,4782)(5652,5382)
\path(2457,3177)(3357,3702)(3432,2277)(2457,2877)
\path(2112,1137)(1362,1137)
\path(5112,1137)(4362,1137)
\path(9162,1212)(8412,1212)
\path(2112,5937)(2712,6762)
\path(2322,5742)(3222,6267)(3297,4842)(2322,5442)
\path(1527,6507)(1947,6327)(2322,7332)(1917,7497)(1527,6507)
\texture{%
555555 55000000 555555 55888888 88555555 55000000 555555 55808080 
80555555 55000000 555555 55888888 88555555 55000000 555555 55888088 
80555555 55000000 555555 55888888 88555555 55000000 555555 55808080 
80555555 55000000 555555 55888888 88555555 55000000 555555 55888088
}
\shade\path(2187,912)(1437,12)(3237,12)(2562,837)(2187,912)
\shade\path(5187,912)(4437,12)(6237,12)(5562,837)(5187,912)
\shade\path(9237,912)(8487,87)(10287,87)(9612,912)(9237,912)
\shade\path(9012,6837)(8637,6462)(7662,7362)(8037,7737)(9012,6837)
\shade\path(5307,6522)(5817,6672)(5517,7947)(5007,7812)(5307,6522)
\shade\path(2562,6987)(2937,6612)(3912,7512)(3537,7887)(2562,6987)
\spline(1977,3207)(987,3762)(537,4587)
\spline(312,6012)(1137,8337)(4287,8337)
\spline(1887,5862)(1587,6162)(1662,6462)
\spline(9837,5787)(10137,6087)(10062,6387)
\spline(9612,7362)(8397,8502)(4797,8442)
\spline(5292,5787)(4587,6192)(4512,6522)
\path(4392,7602)(4497,8007)
\path(5517,5832)(5592,6612)
\path(5322,7902)(4842,8172)
\spline(2112,7437)(2412,7962)(4287,8262)
%
\dottedline{\customdotgapb}(2434.737,1338.696)(2449.312,1497.660)
(2446.980,1546.823)(2439.984,1589.722)(2412.000,1662.000)(2377.502,1699.087)
(2326.638,1727.114)(2265.823,1749.329)(2201.471,1768.984)(2139.998,1789.328)
(2087.819,1813.612)(2037.000,1887.000)(2055.251,1938.779)(2105.718,1977.758)
(2177.722,2008.298)(2218.462,2021.765)(2260.582,2034.758)(2302.747,2047.820)
(2343.621,2061.497)(2416.156,2092.878)(2467.509,2133.259)(2487.000,2187.000)
(2466.953,2241.951)(2414.249,2285.269)(2340.045,2320.278)(2298.367,2335.705)
(2255.497,2350.301)(2212.831,2364.482)(2171.763,2378.662)(2099.997,2408.683)
(2051.357,2443.688)(2037.000,2487.000)(2068.995,2513.195)(2135.370,2520.503)
(2208.810,2529.809)(2262.000,2562.000)(2347.828,2761.297)(2365.781,3102.636)
(2341.566,3256.758)(2267.856,3508.360)(2214.831,3632.490)(2187.000,3687.000)
(2119.618,3742.832)(2071.100,3764.742)(2019.589,3785.906)(1970.254,3808.770)
(1928.265,3835.777)(1898.791,3869.372)(1887.000,3912.000)(1905.703,3978.284)
(1958.016,4030.238)(2032.498,4072.254)(2074.477,4090.908)(2117.707,4108.725)
(2160.760,4126.253)(2202.204,4144.042)(2274.546,4182.599)(2323.291,4228.787)
(2337.000,4287.000)(2313.005,4334.178)(2260.534,4366.135)(2189.217,4387.760)
(2149.501,4396.225)(2108.685,4403.940)(2067.972,4411.517)(2028.567,4419.565)
(1958.494,4439.525)(1887.000,4512.000)(1903.479,4560.629)(1952.731,4597.589)
(2024.051,4627.124)(2064.642,4640.434)(2106.735,4653.480)(2148.993,4666.792)
(2190.077,4680.901)(2263.372,4713.631)(2315.914,4755.916)(2337.000,4812.000)
(2297.743,4882.729)(2255.201,4908.026)(2204.839,4930.050)(2152.247,4951.380)
(2103.015,4974.596)(2017.628,5105.422)(2011.410,5182.361)(2028.551,5348.516)
(2068.667,5508.914)(2158.200,5738.003)(2851.487,6724.650)
%
\dottedline{\customdotgapb}(9470.745,1407.226)(9478.324,1449.403)
(9484.737,1488.696)(9496.980,1590.915)(9496.980,1696.823)
(9462.000,1812.000)(9427.502,1849.084)(9376.638,1877.109)(9189.998,1939.325)
(9137.819,1963.611)(9087.000,2037.000)(9105.251,2088.779)(9155.718,2127.758)
(9227.722,2158.298)(9352.747,2197.820)
(9466.156,2242.878)(9517.509,2283.259)(9537.000,2337.000)(9516.952,2391.951)
(9305.494,2500.301)(9101.355,2593.688)(9087.000,2637.000)(9118.998,2663.195)
(9258.807,2679.809)(9348.278,2774.456)(9421.879,3097.746)(9391.562,3406.754)
(9291.950,3722.715)(9264.830,3782.488)(9237.000,3837.000)
(9169.623,3892.828)(9121.107,3914.737)(9069.596,3935.902)(9020.261,3958.767)
(8978.271,3985.776)(8937.000,4062.000)(9008.011,4180.243)(9210.757,4276.257)
(9373.291,4378.788)(9387.000,4437.000)(9363.005,4484.178)(9239.220,4537.757)
(9199.504,4546.221)(9117.977,4561.512)(9008.498,4589.520)
(8937.000,4662.000)(8949.897,4714.019)(9276.562,4898.495)(9622.811,5178.000)
(9705.580,5284.601)(9743.877,5362.146)(9762.136,5444.323)(9744.737,5553.792)
(9657.996,5665.256)(9537.411,5753.958)(8687.392,6642.609)
%
\dottedline{\customdotgapb}%
(5434.737,1338.696)(5412.000,1662.000)(5377.502,1699.084)
(5087.819,1813.611)(5037.000,1887.000)(5055.251,1938.779)(5105.718,1977.758)
(5343.621,2061.497)(5416.156,2092.878)(5467.509,2133.259)(5487.000,2187.000)
(5466.952,2241.951)(5414.248,2285.269)(5340.042,2320.278)(5298.364,2335.705)
(5255.494,2350.301)(5212.827,2364.482)(5171.758,2378.662)(5099.993,2408.683)
(5051.355,2443.688)(5037.000,2487.000)(5068.998,2513.195)(5135.370,2520.503)
(5208.807,2529.809)(5262.000,2562.000)(5298.278,2624.456)(5326.717,2691.113)
(5347.827,2761.297)(5366.864,2871.704)(5371.879,2947.746)(5365.777,3102.633)
(5341.562,3256.754)(5267.852,3508.357)(5214.830,3632.488)(5187.000,3687.000)
(5119.623,3742.828)(5071.107,3764.737)(5019.596,3785.902)(4970.261,3808.767)
(4928.271,3835.776)(4898.794,3869.372)(4887.000,3912.000)(4905.700,3978.287)
(4958.011,4030.243)(5032.493,4072.259)(5074.473,4090.913)(5117.704,4108.729)
(5337.000,4287.000)(5312.413,4335.333)(5258.506,4370.094)(5185.415,4395.182)
(4952.410,4451.400)(4887.000,4512.000)(4910.194,4554.275)(4967.727,4579.818)
(5197.687,4612.111)(5248.675,4619.503)(5298.479,4629.056)(5345.878,4641.563)
(5519.412,4846.555)(5519.526,4886.090)(5515.529,4926.568)(5508.161,4967.649)
(5446.680,5170.229)(5434.638,5207.805)(5416.732,5277.303)(5412.000,5337.000)
(5416.616,5377.591)(5424.731,5422.713)(5435.863,5471.706)(5449.534,5523.915)
(5490.000,5578.683)(5530.000,5635.351)(5570.000,5693.263)(5610.000,5751.761)
(5670.000,6625.729)
%
\put(237,5187){\makebox(0,0)[lb]{\(\scriptscriptstyle h-1\)}}
\put(1782,6927){\makebox(0,0)[lb]{\(\scriptscriptstyle h-1\)}}
\put(2862,6987){\makebox(0,0)[lb]{\(\scriptscriptstyle h-2\)}}
\put(4280,6852){\makebox(0,0)[lb]{\(\scriptscriptstyle h-1\)}}
\put(5232,7062){\makebox(0,0)[lb]{\(\scriptscriptstyle h-3\)}}
\put(8217,7032){\makebox(0,0)[lb]{\(\scriptscriptstyle 1\)}}
\put(9572,6807){\makebox(0,0)[lb]{\(\scriptscriptstyle h-1\)}}
\put(2232,312){\makebox(0,0)[lb]{\(1\)}}
\put(5232,312){\makebox(0,0)[lb]{\(2\)}}
\put(9057,237){\makebox(0,0)[lb]{\(h-2\)}}
\put(2907,2862){\makebox(0,0)[lb]{\(1\)}}
\put(1737,2697){\makebox(0,0)[lb]{\(v\)}}
\put(6207,5412){\makebox(0,0)[lb]{\(1\)}}
\put(8682,5412){\makebox(0,0)[lb]{\(1\)}}
\put(4782,8592){\makebox(0,0)[lb]{\(r\)}}
\put(657,1287){\makebox(0,0)[lb]{\(d_{1}\)}}
\put(2667,1317){\makebox(0,0)[lb]{\(t_{1}\)}}
\put(4002,1392){\makebox(0,0)[lb]{\(d_{2}\)}}
\put(5547,1422){\makebox(0,0)[lb]{\(t_{2}\)}}
\put(7272,1422){\makebox(0,0)[lb]{\(d_{k}\)}}
\put(9600,1527){\makebox(0,0)[lb]{\(t_{k}\)}}
\put(1287,4992){\makebox(0,0)[lb]{\(s_{1}\)}}
\put(4977,4872){\makebox(0,0)[lb]{\(s_{2}\)}}
\put(9597,4902){\makebox(0,0)[lb]{\(s_{k}\)}}
\put(2877,5412){\makebox(0,0)[lb]{\(1\)}}
\end{picture}
%
\end{center}
}}
%
\afigcap{7}{The transformed graph \protect\(G'\protect\)}
%
\end{figure*}
%
\apar{Proof of Theorem 4-2}
We prove that OPT-\textsupscript{VPL}{1-m} replies \emph{True} on
\(G'\) with \(r\) as the root iff ND40 replies \emph{True} on \(G\)\@.
In the proofs we use the following terminology:
%
\begin{itemize}
%
\item A node \(v\) with \(\loadonnode(v)=L\) is called \emph{saturated}\@.
%
\item A route from \(v\) to \(r\) is said to go \emph{via} a node
\(y\) if the route includes two VPs that are concatenated in \(y\)\@.
%
\item A route from \(v\) to \(r\) is said to go \emph{through} \(y\)
if \(y\) is included in one of the VPs that form the route\@.
%
\item In a minimal VPL, the (single) VP that starts at a node \(v\)
and is used (as a first VP) in the path to \(r\) is called the VP
\emph{from}~\(v\)\@.
%
\end{itemize}
%
\begin{alabsubtext}{Lemma}{10}{}
%
The limiter and extender have the following properties:
%
\begin{enumerate}
%
\item[1.] Given a node \(v\) with a limiter \(\limiter_{p}(v)\), the route
from \(v\) to \(r\) is no more than \(h-p\) hops\@.
%
\item[2.] Given a node \(v\) with a limiter \(\limiter_{p}(v)\), then the
VPs that include \(v\) are from \(v\) itself and from its limiter,
plus at most one additional~VP\@.
%
\item[3.] Given two nodes \(v,w\) with a limiter \(\limiter_{q}(v)\) and
an extender \(\extender_{p}(v,w)\), then a route through \(v\) and
\(w\) includes at least \(p-1\) complete VPs (excluding the VPs that
go through \(v\) and~\(w\))\@.
%
\end{enumerate}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{10}{}
\prooffontshape
%
We divide the proof into the three cases:
%
\paragraph{Case 1}
%
Since \(c_{v}\) is connected to a node \(a_{1}\) of an extender in
\(\limiter_{p}(v)\), its VP can either end at \(a_{1}\) or continue
(toward \(v\))\@. If it continues, then the VP from \(a_{1}\) must also
go through \(a_{2}\) (there is no other way to connect \(r\)), and
\(\loadonnode(a_{2})>L\)\@. Therefore it stops at \(a_{1}\)\@. From
similar considerations, the VP from \(a_{2}\) stops at \(a_{3}\) and
finally, the VP from \(a_{p}\) stops at \(v\), otherwise, there are
two VPs that must go through some node \(u\in U\) and hence more than
\(k\) VPs that go through some \(s_{i}\), causing
\(\loadonnode(s_{i})>L\) for some \(s_{i}\)\@. Therefore, \(v\) must
connect \(r\) using \(h-p\) hops or less (the case when \(p=1\) is
trivial)\@.
%
\paragraph{Case 2}
%
Every VP from \(b_{v}\) in \(\limiter_{p}(v)\) goes through \(v\),
plus one VP from \(v\) and one from \(a_{p}\), a total of
\(L-3+1+1=L-1\), leaving one extra VP through~\(v\)\@.
%
\paragraph{Case 3}
%
The proof resembles the one of Case 1, with the difference that the VP
from \(a_{1}\) does not go through \(v\) because if it does, \(v\) is
saturated, and no other VP can go through~\(v\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 10}}
\end{alabsubtext}
%
\apar{Proof of Theorem 4-3}
\begin{alabsubtext}{Proposition}{1}{}
%
In every \textsupscript{VPL}{1-m} on \(G'\), the load on every node
\(v\in U\) is composed of one VP from \(v\), one VP that includes
\(v\) from the \(L-2\) nodes in \(\extender_{1}(v)\), and no more than
one additional VP, which we term the \emph{extra VP of \(v\)}\@. In
every \(t_{f}i\), the load is composed of the same VPs and one VP from
\(d_i\), hence with no extra~VP\@.
%
\end{alabsubtext}

\begin{alabsubtext}{Lemma}{11}{}
%
If there exists a solution for OPT-\textsupscript{VPL}{1-m} on \(G'\),
then there are \(k\) disjoint paths in \(G\) between every \(s_{i}\)
and~\(t_{i}\)\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{11}{}
\prooffontshape
%
\apar{Proof of Lemma 11-1}
By the previous Lemma, the route from \(t_{k}\) includes no more than two
VPs\@. This route cannot go through any \(\extender_{h-1}(v,r)\),
and it cannot go through \(s_{i}\), \(i\neq k\) because of the
\(\extender_{h-i+1}(s_{i},r)\) which adds at least \(k+2-(k+1)+1-1=1\)
VPs in the route from \(s_{i}\) to \(r\) (by Lemma~10), excluding the
VP to \(r\) and the VP from \(t_{k}\) through \(s_{i}\) (a total of
three VPs)\@. Therefore, the route from \(t_{k}\) goes through~\(s_{k}\)\@.
%
\apar{Proof of Lemma 11-2}
From similar considerations, the route from \(t_{k-1}\) cannot go
through \(s_{i}\), for \(i<k-1\)\@. Also, it cannot go through
\(s_{k}\), since the extra VP of \(s_{k}\) was used by the route from
\(t_{k}\)\@. And by repeating this argument, the route from \(t_{i}\)
goes through \(s_{i}\)\@. Note that this route is composed of a single
VP (that includes both \(t_{i}\) and \(s_{i}\)), because
\(\limiter_{i}(t_{i})\) and \(\extender_{h-i+1}(s_{i},r)\) use \(h-1\)
VPs\@. Also note that each of these paths is node disjoint (since every
intermediate node has only one extra VP), and that a path from
\(t_{i}\) does not go through \(t_{j}\), since every \(t_{j}\) is
already saturated (because of~\(d_{j}\))\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 11}}
\end{alabsubtext}
%
\begin{alabsubtext}{Lemma}{12}{}
%
If there are \(k\) disjoint paths between \(s_{i}\) and \(t_{i}\)
respectively, then there exists a solution for
OPT-\textsupscript{VPL}{1-m} on \(G'\) with \(L=n\), \(h=k+2\)\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{12}{}
\prooffontshape
%
Build a \textsupscript{VPL}{1-m} in the following manner:
%
\begin{itemize}
%
\item Create a VP between every \(b_{i}^{v}\) and \(v\)\@.
%
\item Create a VP between every \(v\in U\) to \(a_{1}\) in
\(\extender_{h-1}(v,r)\), and a VP between every \(a_{p}\) in
\(\extender_{p}(x,r)\) to \(r\) (for every \(x\) for which such an
extender exists)\@.
%
\item Connect \(c_{v}\) to \(a_{1}\) of the extender in every
\(\limiter_{p}(v)\) by a VP, and \(a_{p}\) to~\(v\)\@.
%
\item Create a VP between every \(a_{i}\) to \(a_{i+1}\) in every
extender (if \(p=0\) in \(\extender_{p}(u,v)\) then connect \(u\) and
\(v\) by a~VP)\@.
%
\item Connect \(d_{i}\) to \(t_{i}\) for every \(i\in\{1,\dots,k\}\)\@.
%
\item Connect every \(t_{i}\) to \(a_{1}\) in
\(\extender_{p}(s_{i},r)\) using the path obtained by ND40 through
\(s_{i}\) (as indicated by the dotted lines in Figure~7)\@.
%
\end{itemize}
%
It is easy to verify that \(\loadonnode(\Psi)\leq L\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 12}}
\end{alabsubtext}
%
\apar{Proof of Theorem 4-4}
By Lemma~11, if there exists a \textsupscript{VPL}{1-m} on \(G'\),
then there exist \(k\) disjoint paths from \(s_{i}\) to
\(t_{i}\) in \(G\)\@. By Lemma~12, if there are \(k\) such paths, then
there is a \textsupscript{VPL}{1-m} on \(G'\), hence our
transformation is correct\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 4}}
\end{alabsubtext}
%
\asubsection{A.2}{NP-Completeness Result for the
\protect\textsupscript{VPL}{m-m} Problem}
%
\apar{A.2-1}
The proof that the \textsupscript{VPL}{m-m} problem is NP-complete is
based on the following NP-complete problem\@.
%
\begin{description}
%
\item[\problemlabel{Problem:}] The Symmetric Forwarding Index Problem
(SFI) \cite{cj96-04-23}.
%
\item[\problemlabel{Instance:}] An undirected graph \(G=(V,E)\), an
integer \(k>0\). 
%
\item[\problemlabel{Question:}] Does there exist a set \(R\) of
\(\binom{\setsize{V}}{2}\) undirected paths in \(G\) such that for
every pair \(x,y\in V\) there exists a path in \(R\) whose endpoints
are \(x\) and \(y\), and the number of paths in \(R\) that go through
any node \(v\), for which \(v\) is not an endpoint, does not
exceed~\(k\)\@?
%
\end{description}
%
\apar{A.2-2}
The \textsupscript{VPL}{m-m} problem is formalized as the following
decision problem\@.
%
\begin{description}
%
\item[\problemlabel{Problem:}] The optimal \(h\)-hop \textsupscript{VPL}{m-m}
problem (OPT-\textsupscript{VPL}{m-m}(\(h\))).
%
\item[\problemlabel{Instance:}] An undirected graph \(G=(V,E)\), an
integer \(L>0\).
%
\item[\problemlabel{Question:}] Assuming \(\mu=\infty\), does there exist an
\(h\)-feasible \textsupscript{VPL}{m-m}, \(\Psi\), on \(G\) such that
\(\loadonnode(\Psi)\leq L\)\@?
%
\end{description}
%
\apar{A.2-3}
We first reduce the OPT-\textsupscript{VPL}{m-m} (\(1\)) problem to
SFI, and then reduce OPT-\textsupscript{VPL}{m-m} (\(h+2\)) to
OPT-\textsupscript{VPL}{m-m} (\(h\)) for every \(h\), by this proving
that OPT-\textsupscript{VPL}{m-m}(\(h\)) is NP-complete for every odd
\(h\)\@. A proof that OPT-\textsupscript{VPL}{m-m}(\(2\)) is NP-complete
would suffice to extend this result to every \(h>0\)\@.
%
\begin{alabsubtext}{Lemma}{13}{}
%
OPT-\textsupscript{VPL}{m-m}(\(1\)) is NP-complete\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{13}{}
\prooffontshape
%
Given an instance of SFI, we define an instance of
OPT-\textsupscript{VPL}{m-m} (\(1\)) with the same graph \(G\) and
\(L=k+\setsize{V}-1\)\@. This proof is simple, since the only difference
between the problems is that in SFI a path is not considered part of
the ``load'' on the endpoint nodes, while in
OPT-\textsupscript{VPL}{m-m}(\(1\)) it is considered as part of the
load\@. However, since there are
\(n-1\) paths in \(R\) for which a given node is an endpoint, the load
limit must be increased by \(\setsize{V}-1\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 13}}
\end{alabsubtext}
%
{\sloppy
\begin{alabsubtext}{Lemma}{14}{}
%
OPT-\textsupscript{VPL}{m-m}(\(h+2\)) is NP-complete if
OPT-\textsupscript{VPL}{m-m}(\(h\)) is \hbox{NP-complete}\@.
%
\end{alabsubtext}
}
%
\begin{alabsubtext}{Proof of Lemma}{14}{}
\prooffontshape
%
\apar{Proof of Lemma 14-1}
Let a graph \(G=(V,E)\) and \(L>0\) be an instance of
OPT-\textsupscript{VPL}{m-m} (\(h\)), with
\(\setsize{V}=n\)\@. Construct a graph \(G'=(V',E')\) by initially
taking \(G'\) as \(G\) and then connecting \(M=n L\) new nodes
\(\{w_{v}^{i}\}_{i=1}^{M}\) to every node \(v\in V\)\@.
%
\apar{Proof of Lemma 14-2}
We show that there exists a solution \(\Psi\) to
OPT-\textsupscript{VPL}{m-m}(\(h\)) on \(G\) with load
\(\loadonnode(\Psi)\leq L\) iff there is a solution \(\Psi'\) to
OPT-\textsupscript{VPL}{m-m}(\(h+2\)) on \(G'\) with load
\(\loadonnode(\Psi)\leq L'=L+M\)\@. Assume
\(\Psi\) is a solution \(\Psi\) to
OPT-\textsupscript{VPL}{m-m}(\(h\)), and add VPs from every
\(w_{v}^{i}\) to \(v\)\@. The resulting VPL \(\Psi'\) is a solution to
OPT-\textsupscript{VPL}{m-m} (\(h+2\)) since the distance in \(\Psi\)
between every pair of nodes \(a,b\in V\) satisfies
\(\hopcount_{\mu}(a,b)\leq h\), and therefore the distance in
\(\Psi'\) between every \(w_{a}^{i}\) and \(w_{b}^{j}\) obeys
\(\hopcount_{\mu}(w_a^i,w_b^j)\leq h+2\), and
\(\hopcount_{\mu}(a,w_b^i)\leq h+1\)\@. Since the load in \(\Psi\) is
bounded by \(L\) at each node, the load in \(\Psi'\) is clearly
bounded by~\(L'\)\@.
%
\apar{Proof of Lemma 14-3}
On the other hand, if there exists a solution \(\Psi'\) to
OPT-\textsupscript{VPL}{m-m}(\(h+2\)) on \(G'\) then two cases are
possible:
%
\paragraph{Case 1}
%
\apar{Proof of Lemma 14-4}
For every \(a,b\in V\) in \(\Psi'\) \(\hopcount_{\mu}(a,b)\leq h\)\@. In
this case, we may take the VPs whose endpoints are in \(V\) as a
solution \(\Psi\) to the OPT-\textsupscript{VPL}{m-m}(\(h\))
problem\@. It is clear that
\(\Psi\) uses only nodes from \(G\) (a simple path from \(a\) to \(b\)
cannot include any \(w_{x}^{i}\)), and that the solution is
\(h\)-feasible\@. To show that \(\loadonnode(\Psi)\leq L\), note that
each node in \(x\in V\) has at least load \(M\) from its neighbors
\(w_{x}^{i}\)\@. This leaves only \(L\) for VPs between nodes in~\(V\)\@.
%
\paragraph{Case 2}
%
\begin{sloppypar}
\apar{Proof of Lemma 14-5}
Otherwise, there exists a pair of nodes \(a,b\in V\) for which
\({\hopcount_{\mu}(a,b)>h}\) in~\(\Psi'\)\@. Regard the sets of nodes
\(W_{a}=\setof{w_{a}}{1\leq i\leq M}\) and
\(W_{b}=\setof{w_{b}^{i}}{1\leq i\leq M}\)\@. If there exists a
pair of nodes \(x_{a}\in W_{a}\), \(x_{b}\in W_{b}\) which are
included only in the VPs \((x_{a},a),(x_{b},b)\in E_{\Psi}\), then the
path between \(x_{a}\) and \(x_{b}\) must include the path between \(a\)
and \(b\), and hence
\(\hopcount_{\mu}(x_a,x_b)=\hopcount_{\mu}(a,b)+2>h+2\)---a
contradiction\@. For this reason, either all nodes in \(W_{a}\) or all
nodes in \(W_{b}\) (without loss of generality, assume it is
\(W_{a}\)) are included in VPs that include also a neighbor of
\(a\)\@. By the pigeonhole principle, there exists some neighbor
\(c\in V\) that is included in at least \(\frac{M}{n}\) such VPs\@. Now,
since every node \(w_{c}^{j}\) adds to the load on \(c\) as well, we
get  \(\loadonnode(c)\geq M+\frac{M}{n}>M+L=L'\)---a contradiction\@.
\end{sloppypar}
%
\apar{Proof of Lemma 14-6}
Note that if there exists a VP \((w_{a}^{i},w_{c}^{j})\) in \(\Psi'\),
which is considered in the second component of the above sum (i.e., as
a VP from \(w_{c}^{j}\)), there must be another VP from \(w_{c}^{j}\)
that contributes to the first component of this sum as well, since
\((w_{a}^{i},w_{c}^{j})\) is part of the path from \(w_{a}^{i}\) to
some node \(x_{b}\) in~\(W_{b}\)\@. 
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 14}}
\end{alabsubtext}
%
\begin{alabsubtext}{Theorem}{5}{}
%
OPT-\textsupscript{VPL}{m-m} (h) is NP-complete for every odd \(h>0\)\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{5}{}
\prooffontshape
%
The proof follows directly from the previous two lemmata by induction
on~\(h\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 5}}
\end{alabsubtext}
%
\end{articletext}
%
\begin{articlebib}
%
\bibliographystyle{\the\rbibstyle}
\bibliography{cj96-03}
%
\end{articlebib}
%
\end{document}
