Aleksej Di Salvo and Guido Proietti:
"Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor"
Abstract: We consider a 2-edge connected, undirected graph $G=(V,E)$, with
$n$ nodes and $m$ non-negatively real weighted edges, and a single
source shortest paths tree (SPT) $T$ of $G$ rooted at an arbitrary
node $r$. If an edge in $T$ is temporarily removed, it makes sense
to reconnect the nodes disconnected from the root by adding a
single non-tree edge, called a swap edge, instead of
rebuilding a new optimal SPT from scratch. In the past, several
optimality criteria have been considered to select a best possible
swap edge. In this paper we focus on the most prominent one, that
is the minimization of the average distance between the root and
the disconnected nodes. To this respect, we present an
$O(m\log^2n)$ time and linear space algorithm to find a best swap
edge for every edge of $T$, thus improving for $m = o \left(
n^2/\log^2 n \right)$ the previously known $O(n^2)$ time and space
complexity algorithm.
Alessandro Ferrante and Mimmo Parente:
"Existence of Nash Equilibria in Selfish Routing problems"
Abstract: The problem of routing traffic through a congested network is studied.
The framework is that described by Koutsoupias and Papadimitriou where
the network is constituted by m parallel links, each having a finite
capacity and there are n selfish agents wishing to route their
traffic through one of these links: thus the problem sets naturally in
the context of noncooperative games. Given the lack of coordination
among the agents in large networks, much effort has been lavished in
the framework of mixed Nash equilibria where the agent's routing
choices are regulated by probabilistic distribution, one for each
agent, which let the system reach thus a stochastic steady state from
which no agent is willing to deviate unilaterally. Recently
Mavronicolas and Spirakis have investigated fully mixed equilibria,
where agents have all non zero probabilities to route their traffics
on the links. Here we concentrate on constrained situations where some
agents are forbidden to route their traffic on some links: in this
case we show that at most one Nash equilibrium may exist and we give
necessary and sufficient conditions on its existence; the conditions
relating the traffic load of the agents. We study also a dynamic
behaviour of the network, establishing under which conditions the
network is still in equilibrium when some of the constraints are
removed. All these conditions are effective in the sense that given a
set of yes/no routing constraints on each link for each agent, we
provide the probability distributions that achieve the unique Nash
equilibrium associated to the constraints (if it exists).
Anat Bremler-Barr and Leah Epstein:
"Path layout on tree networks: Bounds in different label switching models"
Abstract: Path Layout is a fundamental graph problem in label switching protocols. This problem is raised in various protocols such as the traditional ATM protocol and MPLS which is a new label switching protocol standardized recently by the IETF.
Path layout is essentially the problem of reducing the size of the
label-table in a router. The size is equivalent to the number of different paths that pass through the router, or start from it.
A reduction in the size can be achieved by choosing a relatively small number of paths, from which a larger set is composed using concatenation.
In this paper we deal with three variations of the Path Layout
Problem according to the special characteristics of paths in three label switching protocols, MPLS, ATM and TRAINET. We focus on tree networks, and show an algorithm which finds label-tables of small size, while permitting concatenation of at most k paths. We prove that this algorithm gives worst case tight bounds (up to constant factor) for all three models. The bounds are given as a function of the size of the tree, and the maximum degree.
Arvind Gupta, Jan Manuch and Ladislav Stacho:
"Fault tolerant forwarding and optical indexes - a design theory approach"
Abstract: We study the problem of designing fault tolerant routings in complete and complete bipartite optical networks. We show that this problem has strong connections to various fundamental problems in design theory. Using design theory approach, we find optimal $f$-tolerant arc-forwarding indexes for complete networks of a prime power order, and all complete bipartite networks. Similarly, we find almost exact values for $f$-tolerant optical indexes for these networks. Our work motivates an interesting relaxation of an extensively studied problem on mutually orthogonal Latin squares.
Bogdan Chlebus and Mariusz Rokicki:
"Asynchronous Broadcast in Radio Networks"
Abstract:
We study asynchronous packet radio networks in which
transmissions among nodes may be delayed.
We consider the task of broadcasting a message generated by a source node.
The timing of arrivals of messages is controlled by adversaries.
We consider three different adversaries.
The edge adversary can have a transmitted message delivered at different
times to different recipients.
The crash adversary is the edge one augmented by a power to crash nodes.
The node adversary can have a message received at arbitrary times, but
simultaneously by all the recipients.
A protocol specifies for each node how many times the message is
retransmitted by this node, after it has been received.
The total number of transmissions of nodes is defined to be a measure
of performance of a broadcast protocol, and is called its work.
The radio network is modeled as a graph and is given as input
to a centralized algorithm.
An aim of the algorithm could be either to find a broadcast protocol,
possibly with additional properties,
or to verify correctness of a given protocol.
We give an algorithm to find a protocol correct against the
edge adversary.
The obtained protocol is work-exponential in general.
This is an inherent property of the problem, as is justified by a lower bound.
We develop a polynomial algorithm to verify correctness of a given
protocol for a given network against the edge adversary.
We show that a problem to decide if there exists a protocol,
for a given network and of a specified work performance, is NP-hard.
We extend some of these results to the remaining two adversaries.
Chryssis Georgiou, Peter Musial, and Alex Shvartsman:
"Long-Lived Rambo: Trading Knowledge for Communication"
Abstract: Shareable data services providing consistency guarantees,
such as atomicity (linearizability), make building dynamic
distributed systems easier. In general it is difficult
to combine the guarantee of linearizability with efficiency
and practicality. A reconfigurable linearizable data service,
called \RAMBO{}, was developed by Lynch and Shvartsman.
This service guarantees consistency under dynamic conditions
involving asynchrony, message loss, node crashes, and new
node arrivals. The specification of the original algorithm
is given at an abstract level aimed at concise presentation
and formal reasoning about correctness. The algorithm
propagates information by means of gossip messages.
If the service is in use for a very long time, the size and
the number of gossip messages may grow without bound.
First, \RAMBO{} allows new nodes to join the computation,
but it does not allow the nodes to leave gracefully (other
than failing). Given that in asynchronous systems failure
detection is difficult, it may be impossible to distinguish
departed nodes from the nodes that crash. Second, \RAMBO{}
gossips information without regard for what may already
be known.
%
This paper presents a consistent data service for
\emph{long-lived} objects that improves on \RAMBO{} in two ways:
it includes an incremental communication protocol and a leave
service. Together with \RAMBO{} object management algorithm,
this yields a practical and long-lived atomic data service.
The new protocol taking advantage of the local knowledge, and
it carefully manages the size of messages by removing redundant
information from messages, while the leave service allows the
nodes to leave the system gracefully. The incremental
communication protocol is designed to ensure correctness in
the asynchronous settings with message loss and node crashes.
The new algorithm is formally proved correct by forward simulation
using levels of abstraction. By trading knowledge for communication
the algorithm substantially reduces the number and the size of
gossip messages. An experimental implementation of the system was
developed for networks-of-workstations. The paper includes
analytical and preliminary empirical results that illustrate
the advantages of the new algorithm.
Deshi Ye and Hu Zhang:
"The Range Assignment Problem in Static Ad-Hoc Networks on Metric Spaces"
Abstract:
In this paper we study the range assignment problem in static ad-hoc networks on
metric spaces. We consider the $h$-strong connectivity and $h$-broadcast
problems on trees, high dimensional Euclidean spaces and general metric spaces.
Both homogeneous and non-homogeneous cases are explored. We prove that the
$h$-broadcast problem is polynomial solvable on trees and there exists an
$O(n^2)$-approximation algorithm for the $h$-strong connectivity problem on
trees. Furthermore, we propose a probabilistic $O(\log n \log\log
n)$-approximation algorithm for the $h$-broadcast problem and a probabilistic
$O(n^2 \log n \log\log n)$-approximation algorithm for the $h$-strong
connectivity problem on high dimensional Euclidean spaces and general metric
spaces, where $n$ is the number of stations. In the case of high dimensional
Euclidean spaces and general metric spaces, if the distance-power gradient
$\alpha\leq 1+O(\log\log\log n/\log\log n)$, an $O(\log^{\al} n)$-approximation
algorithm and an $O(n^2 \log^{\al} n)$-approximation algorithm are developed for
the $h$-broadcast problem and the $h$-strong connectivity problem, respectively.
They are the first algorithms for the range assignment problem in static ad-hoc
networks on general metric spaces. And the approximation ratio of $O(\log n
\log\log n)$ for the $h$-broadcast problem on general metric spaces is close to
the known lower bound $O(\log n)$ [G. Rossi, The Range Assignment Problem in
Static Ad-Hoc Wireless Networks, Ph.D. Thesis, 2003].
Deshi Ye, Guochuan Zhang:
"On-line scheduling of parallel jobs"
Abstract: We study an on-line parallel job scheduling problem, where jobs
arrive over list. A parallel job may require a number of machines
for its processing at the same time. Upon
the arrival of a job, its processing time and the number of
requested machines become known, and it must be scheduled
immediately without any knowledge of future jobs. We present a
8-competitive on-line algorithm, which improves the previous upper
bound
of 12 by Johannes (2001). Furthermore, we investigate two
special cases
and show better bounds.
Eric Angel, Evripidis Bampis, Fanny Pascual:
"Traffic grooming in a passive star WDM network"
Abstract: We consider the traffic grooming problem in passive WDM star networks. Traffic grooming is concerned with the development of techniques for combining low speed traffic components onto high speed channels in order to minimize network cost. We first prove that the traffic grooming problem in star networks is NP-hard for a more restricted case than the one considered in [1]. Then, we propose a polynomial time algorithm for the special case where there are two wavelengths per fiber, using matching techniques. Furthermore, we propose two reductions of our problem to two combinatorial optimization problems (the constrained multiset multicover problem, and the demand matching problem), allowing us to obtain a polynomial time log(2C) (resp. 2+(13/16)) approximation algorithm for the minimization (resp. maximization) version of the problem, where $C$ is the capacity of each wavelength.
[1]: R. Dutta and G.N. Rouskas, "On Optimal Traffic Grooming in WDM Rings", IEEE Journal on selected areas in communications, Vol. 20, No. 1, January 2002.
Fertin, G.and Raspaud, A. and Sykora, O.:
"No-Hole L(p,0) Labelling of Cycles, Grids and Hypercubes"
Abstract: In this paper, we address a particular case of the general problem of
lambda labellings, concerning frequency assignment for
telecommunication networks. In this model, stations within a given
radius r must use frequencies that differ at least by a value p,
while stations that are within a larger radius r'>r must use
frequencies that differ by at least another value q. The
aim is to minimize the span of frequencies used in the network. This
can be modelled by a graph labelling problem, called the
L(p,q) labelling, where one wants to label vertices of the graph G
modelling the network by integers in the range [0;M], while
minimizing the value of M. M is then called the lambda number
of G, and is denoted by $\lambda_q^p (G)$.
Another parameter that sometimes needs to be optimized is the fact that all the possible frequencies (i.e., all the possible values in the span) are used. In this paper, we focus on this problem. More precisely, we want that:
(1) all the frequencies are used and
(2) condition(1) being satisfied, the span must be minimum.
We call this the no-hole L(p,q) labelling problem for G.
Let [0;M'] be this new span and call the $\nu$ number of G the value M', and denote it by $\nu^p_q(G)$.
In this paper, we study a special case of no-hole L(p,q)
labelling, namely where q=0. We also focus on some specific topologies: cycles, hypercubes, 2-dimensional grids and 2-dimensional tori. For each of the mentioned topologies cited above,
we give bounds on the $\nu_0^p$ number and show optimality in some cases. The paper is concluded by giving new results concerning the (general, i.e. not necessarily no-hole) L(p,q) labelling of hypercubes.
Flaminia L. Luccio and Jop F. Sibeyn:
"Tighter Bounds on Feedback Vertex Sets in Mesh-based Networks"
Abstract: In this paper we consider the minimum feedback vertex set problem in graphs, i.e., the problem of finding a minimal
cardinality subset of the vertices, whose removal makes a graph acyclic. The problem is N P-hard for general topologies, but
optimal and near-optimal solutions have been provided for particular networks. In this paper the problem is considered for undirected graphs with the following topologies: two- and higher-dimensional meshes of trees, trees of meshes and pyramid networks. For the meshes of trees and the tree of meshes the results are asymptotically optimal. For the pyramid networks, the presented upper and lower bounds are almost matching.
G.Cordasco, L.Gargano, M. Hammar, A.Negro, V. Scarano:
"F-Chord: Improved Uniform Routing on Chord"
Abstract: We propose a family of novel schemes based on Chord retaining all positive aspects that made Chord a popular topology for routing in P2P networks. The schemes, based on the Fibonacci number system, allow to improve on the maximum/average number of hops for lookups and the routing table size per node.
Janka Chlebikova and Miroslav Chlebik:
"On Approximability of the Independent Set Problem for Low Degree Graphs"
Abstract: We obtain slightly improved upper bounds on efficient
approximability of the Maximum Independent Set problem in graphs
of maximum degree at most B (shortly, B-MaxIS), for small B>=3.
The degree-three
case plays a role of the central problem, as many of the results for
the other problems
use reductions to it. Our careful analysis of approximation
algorithms of Berman and Fujito for 3-MaxIS shows that one can achieve
approximation ratio arbitrarily close to 3-\sqrt{13}/2. Improvements
of approximation factor below 6/5 for this case translate
to improvements
below (B+3)/5 of approximation factors for B-MaxIS for all odd~B.
Consequently, for any odd B>= 3, a polynomial time algorithm for
B-MaxIS
exists with approximation ratio arbitrarily close to
(B+3)/5-[[4(5\sqrt{13}-18)]/5].[(B-2)!!][(B+1)!!].
This is currently the best upper bound for
B-MaxIS for any
odd B, 3<= B<613.
Leszek Gasieniec, Igor Potapov, and Qin Xin:
"Time efficient gossiping in known radio networks"
Abstract: We study here a gossiping problem (all-to-all communication)
in known radio networks, i.e., when all nodes are aware of the
network topology.
We start our presentation with a deterministic algorithm for
the gossiping problem that works in at most $n$ units of a time
in any radio network of size $n$. This is an optimal algorithm
in the sense that there exist radio network topologies, such as:
a line, a star and a complete graph in which the radio gossiping
cannot be completed in less then $n$ units of time.
Further, we show that there isn't any radio network topology
in which the gossiping task can be solved in time
$<\lfloor\log(n-1)\rfloor+2.$ We show also that this lower bound
can be matched from above for a fraction of all possible integer
values of $n;$ and for all other values of $n$ we propose
a solution admitting gossiping in time $\lceil\log(n-1)\rceil+2.$
We show later an ({\sl one-off}\/) optimal radio gossiping in trees.
Finally we study asymptotically optimal $O(D)$-time gossiping
(where $D$ is a diameter of the network) in graphs with max-degree
$\Delta=O(\frac{D^{1-1/(i+2)}}{\log^{i+1} n}),$ for any integer
constant $i\ge 0$ and $D$ large enough.
Luciano Margara, Alessandro Pistocchi, Marco Vassura:
"Perfect Token Distribution on Trees"
Abstract: Load balancing on a multi-processor system consists of redistributing tasks among processors so that all processors end up with roughly the same amount of work to perform. The token distribution problem is a variant of the load balancing problem where
each task has unit-size and it represents an atomic element of work.
We present an algorithm for computing a perfect token distribution
on distributed tree-connected networks having worst-case running time O(TD) (D denotes the diameter of the tree and T denotes the total number of tokens).
This is the first fully decentralized algorithm for computing perfect
token distributions on arbitrary tree-connected networks which does not receive as input any kind of aggregate information about the network (e.g., number of nodes
or total number of tokens).
Michel Paquette, Andrzej Pelc:
"Optimal decision strategies in Byzantine environments"
Abstract: A Boolean value of given a priori probability distribution
is transmitted to a deciding agent by several processes.
Each process fails independently with given probability,
and faulty processes behave in a Byzantine way. A deciding agent has
to make a decision concerning the transmitted value on the basis of messages obtained by processes.
We construct a deterministic decision strategy which has the provably highest probability of correctness.
It computes the decision in time linear in the number of processes.
Decision optimality may be alternatively approached from a local, rather than global, point of view.
Instead of maximizing the total probability of correctness of a decision strategy, we may try to find, for every set of values
conveyed by processes, the conditionally most probable original value that could yield this set.
We call such a strategy locally optimal, as it locally optimizes
the probability of a decision, given a set of relayed values, disregarding the impact of such a choice on the overall
probability of correctness.
We construct a locally optimal decision strategy which again
computes the decision value in time linear in the number of processes. We establish the surprising fact that, in general,
local probability maximization may lead to a decision strategy which does not have the highest probability of correctness. However, if
the probability distribution of the Boolean value to be conveyed is uniform, and all processes have the same failure probability
smaller than 1/2, this anomaly does not occur.
Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Flaminia Luccio, Nicola Santoro, Cindy Sawchuk:
"Mobile Agent Rendezvous When Tokens Fail"
Abstract: The mobile agent rendezvous problem consists of k = 2 or more mobile agents trying to rendezvous or meet in a minimum amount of time on an n node ring network. Tokens and markers have been used successfully to achieve rendezvous when the problem is symmetric, e.g., the network is an anonymous ring and the mobile agents are identical and run the same deterministic algorithm. In this paper, we explore how token failure affects the time required for mobile agent rendezvous under symmetric conditions with different types of knowledge. Our results suggest that knowledge of n is better than knowledge of k in terms of achieving rendezvous as quickly as possible in the faulty token setting.
Paolo Penna and Carmine Ventre:
"Sharing the Cost of Multicast Transmissions in Wireless Networks"
Abstract: We investigate the problem of sharing the cost of a multicast
transmission in a wireless network where each node (radio
station) of the network corresponds to a (set of) user(s) potentially
interested in receiving the transmission. As in the model considered by
Feigenbaum \emph{et al} [2001], users may act \emph{selfishly}
and report a false ``level of interest'' in receiving the
transmission trying to be charged less by the system. We
consider the issue of designing so called \emph{truthful
mechanisms} for the problem of maximizing the \emph{net worth}
(i.e., the overall ``happiness'' of the users minus the cost of the
transmission) for the case of \emph{wireless} networks. Intuitively, truthful
mechanism
guarantee that no user has an incentive in reporting a false
valuation of the transmission.
Unlikely the
``wired'' network case, here the cost of a set of connections
implementing a multicast tree is \emph{not} the sum of the
single edge costs, thus introducing a complicating factor in the
problem. We provide both positive and negative results on the
existence of optimal algorithms for the problem and their use to
obtain VCG truthful mechanisms achieving the same
performances.
Paul Boone, Edgar Chavez, Lev Gleitzky, Evangelos Kranakis, Jaroslav Opatrny, Gelasio Salazar, Jorge Urrutia:
"Morelia Test: Improving the Efficiency of the Gabriel Test and Face Routing in Ad-hoc Networks"
Abstract: An important technique for discovering routes between two nodes in an ad-hoc network involves application of the face routing algorithm on a planar spanner of the network. Face routing on a planar subgraph guarantees message delivery in networks whose geometrical representation contains large holes without any node and having complex contours, where the usual greedy algorithms fail. Existing techniques for constructing a suitable planar spanner involve local tests that eliminate crossings between existing links by deleting some of the links. The existing tests do not test whether the deleted links actually create some crossings and some of the links are deleted needlessly. As a result, the routes in the face routing will have an unnecessarily large number of hops from source to destination. We consider a new local test for preprocessing a wireless network that produces a planar subgraph on which we can apply face routing. The test is relatively simple, requires low overhead and does not unnecessarily eliminate existing links unless it is needed to eliminate a crossing, thus reducing overhead usually associated with multiple hops.
R. Wang, F.C.M. Lau, Y. Liu:
"NP-Complete Results for All-Shortest Paths Interval Routing"
Abstract: $k$-Interval Routing Scheme ($k$-IRS) is a compact routing method that
allows up to $k$ interval labels to be assigned to an arc. A
fundamental problem is to characterize the networks that admit
$k$-IRS. All the problems related to single-shortest path $k$-IRS have
already been shown to be NP-compete. For all-shortest paths $k$-IRS,
the characterization problem remains open for $k\geqslant 1$. We
investigate the time complexity of devising minimal-space all-shortest
paths $k$-IRS and prove that it is NP-complete to decide whether a
graph admits an all-shortest paths $k$-IRS, for every integer
$k\geqslant 3$, as well as whether a graph admits an all-shortest paths
$k$-strict IRS, for every integer $k\geqslant 4$. These are the first
NP-completeness results for all-shortest paths $k$-IRS where $k$ is a
constant and the graph is unweighted. Moreover, the NP-completeness
holds also for the linear case.
Rachel Matichin, David Peleg:
"Approximation Algorithm for Hotlink Assignment in the Greedy Model"
Abstract: Link-based information structures such as the web can be enhanced
through the addition of hotlinks. Assume that each node in the
information structure is associated with a weight representing
the access frequency of the node by users. In order to access a particular node, the user has to follow a path leading to it from
the root node. By adding new hotlinks to the tree, it may be
possible to reduce the access cost of the system, namely, the
expected number of steps needed to reach a leaf from the root,
assuming the user can decide which hotlinks to follow in each step.
The hotlink assignment problem involves finding a set of hotlinks
maximizing the gain in the expected cost.
The paper addresses this problem in the more realistic greedy
user model recently introduced in [GKMP03], and presents
a polynomial time 2-approximation algorithm for the hotlink
assignment problem on trees.
Reuven Cohen, David Peleg:
" Robot Convergence via Center-of-Gravity Algorithms"
Abstract: Consider a group of N robots aiming to converge towards a single
point. The robots cannot communicate, and their only input is
obtained by visual sensors. A natural algorithm for the problem
is based on requiring each robot to move towards the robots'
center of gravity.
The paper proves the correctness of the center-of-gravity algorithm
in the semi-synchronous model for any number of robots,
and its correctness in the fully asynchronous model for two robots.
S. Choplin, L. Narayanan, J. Opatrny:
"Two-Hop Virtual Path Layout in Tori"
Abstract: We consider the problem of D-hop virtual path layout in ATM
(Asynchronous Transfer Mode) networks. Given a physical network and an
all-to-all traffic pattern, the problem consists of designing a virtual network with a given diameter D, which can be embedded in the physical
one with a minimum congestion (the congestion is the maximum load of a
physical link). Here we propose a method to solve this problem when the
diameter is 2. We use this method to give an asymptotically optimal
solution for the 2-hop virtual path layout problem for all-to-all
traffic when the physical network is a mesh, a torus or a chordal ring.
Stefan Dobrev, Paola Flocchini, Nicola Santoro:
"Improved Bounds for Optimal Black Hole Search\\ with a Network"
Abstract: A black hole is a harmful host that destroys incoming agents without
leaving any observable trace of such a destruction. The black hole search problem is to unambiguously determine the location of the
black hole. A team of agents, provided with a network map and
executing the same protocol, solves the problem if at least one agent
survives and, within finite time, knows the location of the black hole.
It is known that a team must have at least two agents. Interestingly, two agents with a map of the network can ocate the black hole with O(n) moves in many highly regular networks; however the protocols used apply only to a narrow class of networks. On the other hand, any universal solution protocol must use Omega(n log n) moves
in the worst case, regardless of the number of agents.
In this paper we present a universal protocol that allows a team of two agents with a network map to locate the black hole using at most O(n + d log d) moves, where d is the diameter of the network. This means that, without losing its universality and without violating the
worst-case \Omega(n log n) lower bound, this algorithm allows two
agents to locate a black hole with Theta(n) cost in a very large
class of (possibly unstructured) networks: those where d = O(n/log n).
Vittorio Biló and Luca Moscardelli:
"The price of anarchy in all-optical networks"
Abstract: In this paper we consider all-optical networks in which a service provider
has to satisfy a given set of communication requests. Each request is charged a cost depending on its
wavelength and on the wavelengthsof the other requests met along its path in the network. Under the
assumption that each request is issued bya selfish agent, we seek for payment strategies which can guarantee the
exisyence of a pure Nash equilibrium,that is of paths to the requests so that no request can lower its cost by
choosing a different path in the network.For such strategies, we bound the loss of performance of the network
(price of anarchy) by comparing the numberof wavelengths used by the worst pure Nash equilibrium with that of a
centralized optimal solution.
Yon Dourisboure and Cyril Gavoille:
"Sparse Additive Spanners for Bounded Tree-Length Graphs"
Abstract: This paper concerns construction of additive stretched spanners with
few edges for $n$-vertex graphs having a tree-decomposition into bags
of diameter at most $\delta$, i.e., the tree-length $\delta$
graphs. For such graphs we construct additive $2\delta$-spanners with
$O(\delta n\log n)$ edges, and additive $6\delta$-spanners with
$O(\delta n)$ edges. We also show a lower bound, and prove that there
are graphs of tree-length $\delta$ for which every multiplicative
$\delta$-spanner (and thus every additive $(\delta-1)$-spanner)
requires $\Omega(n^{1+1/\Theta(\delta)})$ edges.