Maximum number of requests on a path with a given grooming factor

Jean-Claude Bermond, Michel Cosnard, David Coudert, and Stéphane Perennes

Université Côte d'Azur, Inria, CNRS, I3S, Sophia Antipolis, France

October 14, 2024

**Abstract**

We give an optimal solution to the Maximum All Request Path Grooming (MARPG) problem motivated by a traffic grooming application and for its interest for computing lower bounds for the cutwidth of a graph. The MARPG problem consists in finding the maximum number of connections which can be established in a path of size *n*, where each arc has a capacity or bandwidth *C* (grooming factor). A simple greedy solution is obtained by taking all requests of smallest length. However this is not optimal in general since anomalies can exist. We give a complete analysis and the exact number of such anomalies. Then, we establish a formula returning in constant time the value of the optimal solution to the MARPG problem. We also propose a polynomial time algorithm to get the set of requests of an optimal solution. Finally, we establish upper bounds on the number of anomalies, for example the general one is $(5 - 2\sqrt{6})C$. These bounds can be used to get new lower bounds for the cutwidth of a graph.

**Keywords**: grooming; requests; path; cutwidth; coloration of interval graphs.

# 1 Introduction

**The Maximum All Request Path Grooming (MARPG) problem.** The MARPG problem, also known as the *Call Control Problem in Path Networks* in [1], was first motivated by traffic grooming in an optical path network and then by computation of the cutwidth of a graph, but is of interest by itself. It can be stated as follows. We are given a directed path on *n* vertices $P_n$ and a number *C* (capacity or grooming factor). A request $(i, j)$ is routed via the unique subpath of $P_n$ from *i* to *j*. The MARPG problem consists in finding the maximum number of simple requests (any request appears at most once), denoted $T(C, n)$, that can be routed (groomed) together such that at most *C* requests use a given arc of the path. Said otherwise we want that the load of any arc (number of requests whose routing use this arc) does not exceed the capacity *C* of the arc. One can also formulate the problem as: what is the maximum number of connections that can be established in a network where each arc has a given capacity (bandwidth) *C*, the network being here a path ?

The MARPG problem is a particular case of the MRPG (Maximum Request Path Grooming) problem where the set of possible requests is general and not necessarily complete. As noted in [10, 12] there exists a polynomial time algorithm to solve the MRPG problem, and therefore to solve our problem. Indeed the MRPG problem is itself a particular case of the problem of finding a maximum *C*-colorable subgraph of an interval graph considered in [5, 13]. In this problem we are given a set of *n* intervals and a number *C* and we want to find the maximum
number of intervals which can be colored with one of the *C* colors such that two intersecting intervals receive different colors.

The best known algorithm is given in [5] and has time complexity in $O(C + n)$. However, for our applications, we need a closed formula and to the best of our knowledge, this does not exist in the literature. Such a formula is given in Theorem 12.

**Grooming motivation (see [2]).** Let us now explain our first motivation. In the original problem of grooming considered in [7] and [2], to each request is associated a route in the optical network and a wavelength; each request uses at most 1/C of the bandwidth of a wavelength, or equivalently on a given arc there can be at most C requests with the same wavelength. For a given set of requests the objective is to minimize the number of ADMs (Add Drop Multiplexers) used (an ADM is a device used to inject (add) or extract (drop) the traffic of a request from / to a wavelength). This problem has been widely studied in the literature (see the surveys [8, 9, 11, 14]) for various physical network topologies, in particular for unidirectional ring networks. In [2, 7] the physical network is a dipath. In [7] the problem is proved to be NP-complete for a general set of requests. In [2] the problem is modeled as a graph partitioning problem as follows: if the set of requests is represented by a graph *G*, the grooming problem on the path consists in partitioning the edges of *G* into subgraphs $B_w = (V_w, E_w)$, such that for any arc $(i, i+1)$ of the path there are in each subgraph $B_w$ at most *C* edges $(u, v)$ with $u \le i < v$. The objective is to minimize the sum of the number of vertices $|V_w|$ of the subgraphs $B_w$. Here $E_w$ corresponds to the requests with wavelength *w* and $V_w$ to the number of ADM's used for this wavelength. To solve the problem, in particular to obtain lower bounds, it is needed to know what is the maximum number of edges $T(C, p)$ that a subgraph $B_w$ with *p* vertices can contain (for more details see [2], where $T(C, p)$ is called $\gamma(C, p)$). This is exactly the MARPG problem for a dipath.

**Cutwidth motivation (see [3]).** A *layout* of a graph *G* = (*V*, *E*) is a linear ordering π = (*v*₁, ..., *v*ₙ) of the vertices of *G*. The *edge-cut* of a set *X* ⊆ *V* is the set of edges with one end-vertex in *X* and the other in *X* = *V* \ *X*. Its size is denoted by *ec*(*X*, *X*). Let *X*ᵢ = {*v*₁, ..., *v*ᵢ}. The *width* *w*(*G*, π) of a graph *G* with respect to the layout π is the maximum of *ec*(*X*ᵢ, *X*ᵢ) over all *i* ∈ {1, ..., *n* − 1}. The *cutwidth* of a graph *G*, denoted by *cw*(*G*), is the minimum width taken among all the layouts, that is *cw*(*G*) = min{*w*(*G*, π) | π *layout of G*}. Consider the path *P*π = *v*₁...*v*ₙ associated to the layout π = (*v*₁, *v*₂, ..., *v*ₙ). For each edge *e* ∈ *E*, the *request associated to e* by π, denoted by *R*π(*e*), is the subpath of *P*π whose end-vertices are those of *e*. Let *R*π(*G*) be the set of requests associated by π to the edges of *G*. Observe that the load of the edge *v*ᵢ*v*ᵢ₊₁ in *P*π under *R*π(*G*), denoted *l*(*v*ᵢ*v*ᵢ₊₁), is the number of edges *v*ⱼ*v*ᵢ of *G* with *j* ≤ *i* < *l*, that is *ec*(*X*ᵢ, *X*ᵢ). Hence *w*(*G*, π) is the maximum load of an edge of *P*π under *R*π(*G*).

Therefore, **the value $T(C, n)$ is nothing else than the maximum number of edges of a simple graph of order $n$ with cutwidth $C$.** That allows us to get a lower bound for $cw(G)$ which is useful for computing the cutwidth, namely $cw(G) \ge C^*(m, n) = \min\{C \mid m \le T(C, n)\}$ (see [3] for more details). This lower bound is also used in [6] (bound $LB_4$) but with false values for $T(C, n)$.

**Our results.** First, we note that if $C \ge \lfloor n^2/4 \rfloor$, then we can satisfy all the requests and so $T(C, n) = n(n-1)/2$. If $C=1$, the MARPG problem is easy to solve as an optimal solution consists in taking the $n-1$ requests of length 1 (i.e., requests $(i, i+1)$) and so $T(1, n) = n-1$. In that case the grooming problem is also solved for any traffic in [2]. In [2] it is also proven that for $C=2$, $T(2, n) = \lfloor \frac{3n-3}{2} \rfloor$ (and that solves the grooming problem for uniform all to all traffic). The solution is obtained by taking all the requests of length 1 and half of that of length
2 (those of the form $(2j+1, 2j+3)$). The optimum can be easily found for $C \le 6$; in particular for $C=3$ (respectively $C=6$) the maximum is obtained by considering all the requests of length 1 and 2 (resp. 1, 2 and 3, except when $C=6$ and $n=5$ where all the requests can be satisfied and so the request of length 4 can be added).

Based on these results, it was conjectured the “intuitive fact” that the optimum for the MARPG problem was obtained by taking the greedy solution consisting of all the requests of smallest length (this was presented as a result in [6]). However it appears that the conjecture is false (see Section 3).

In this article we will show that an optimal solution consists of $C$ "independent sets" of requests (see the definition in Section 2) ordered by their weights (Theorems 6 and 8). Then, we show in Section 5 how to determine exactly for any $n$ and $C$ the optimal value of $T(C, n)$. Finally, we provide in Section 6 some upper-bounds on this value, and more precisely on the difference between $T(C, n)$ and the number $G(C, n)$ of requests of the greedy solution.

The present paper is a revised, corrected and extended version of [4].

## 2 Definitions and structuring the requests in independent sets

$P_n$ denotes the directed path on $n$ vertices $\{1, 2, \dots, n\}$, with arcs $e_i = (i, i+1), i = 1, \dots, n-1$.

We will define a request $(i, j)$ with $1 \le i < j \le n$ both as a couple of vertices and as the subpath of $P_n$ from vertex $i$ to vertex $j$. The size (or length) of a request $(i, j)$ is defined as $\sigma = j - i$. The set of simple requests is denoted by $R = \{(i, j) | 1 \le i < j \le n\}$, and so $|R| = n(n-1)/2$. For $1 \le \sigma \le n-1$, we denote by $R(\sigma)$ **the set of all the requests of size $\sigma$**. We have $|R(\sigma)| = n - \sigma$ and $R = \bigcup_{\sigma=1}^{n-1} R(\sigma)$.

By definition, the request $(i, j)$ with $1 \le i < j \le n$ loads with load 1 all the arcs of the subpath of $P_n$ from vertex $i$ to vertex $j$. Given a set of requests, the load of an arc $e_i$ is the number of requests of this set containing $e_i$. The load induced by a set of requests on the path $P_n$ is the maximum load of its arcs.

The grooming factor $C$ being given, the **Maximum All Request Path Grooming (MARPG) problem** consists in finding the cardinality of a maximum set of requests that can be groomed together such that the load of any arc of $P_n$ with this set of requests is at most $C$. **The cardinality of such a maximum set of requests will be denoted $T(C, n)$**. One can also ask for the requests themselves that are satisfied in an optimal solution. We note that if $C \ge \lfloor n^2/4 \rfloor$ then we can satisfy all requests and so $T(C, n) = n(n-1)/2$. So **in what follows we suppose that $C < \lfloor n^2/4 \rfloor$**.

There are many ways of structuring the set of requests $R(\sigma)$. In the following we choose to consider maximal sets of independent requests with the same size, where two requests are said to be independent if the associated subpaths have no arc in common.

**Definition 1** For $1 \le t \le \sigma$, we define the **independent set $I(\sigma, t)$** as the subset of $R(\sigma)$ composed of requests of the form $(t + (h-1)\sigma, t + h\sigma)$ where $1 \le h \le \lfloor \frac{n-t}{\sigma} \rfloor$.

Hence, $I(1, 1)$ consists of all requests of size 1, namely the requests $(i, i+1)$. $I(2, 1)$ (resp. $I(2, 2)$) consists of all requests of the form $(2j+1, 2j+2)$ (resp. $(2j+2, 2j+3)$) and so on we have $I(\sigma, t) = \{(t, t+\sigma), (t+\sigma, t+2\sigma), \dots\}$. For example, for $n=11$ we have $I(3, 1) = \{(1, 4), (4, 7), (7, 10)\}$; $I(3, 2) = \{(2, 5), (5, 8), (8, 11)\}$; $I(3, 3) = \{(3, 6), (6, 9)\}$; $I(4, 1) = \{(1, 5), (5, 9)\}$; $I(4, 2) = \{(2, 6), (6, 10)\}$; $I(4, 3) = \{(3, 7), (7, 11)\}$; $I(4, 4) = \{(4, 8)\}$; $I(5, 1) = \{(1, 6), (6, 11)\}$, and for $2 \le t \le 5$, $I(5, t) = \{(t, t+5)\}$ and so on. $I(10, 1) = \{(1, 11)\}$ and $I(10, t)$ is empty for $t \ge 2$.

Note that all requests of $I(\sigma, t)$ are independent and that their number is $w(\sigma, t) = \lfloor \frac{n-t}{\sigma} \rfloor$. In the following, $w(\sigma, t)$ **will be called the weight of the independent set $I(\sigma, t)$**.
We also note that if $t+\sigma > n$, then the set $I$ is empty and so in what follows we will consider only non empty independent sets. Here are some easy properties which will be useful.

**Property 2** For any given $\sigma \le n-1$, the union of all $I(\sigma, t)$ for $1 \le t \le \sigma$ is equal to $R(\sigma)$ and so the union of all independent sets $I(\sigma, t)$, for all the ordered pairs $(\sigma, t)$ with $1 \le t \le \sigma \le n-1$, is exactly the set $R$.

**Property 3**

1. The load induced by a set of $k$ independent sets is at most $k$.

2. Let $s \le n/2$. The load induced by a set of $k$ independent sets $I(\sigma, t)$, with $1 \le \sigma \le s$, is exactly $k$ on all the arcs $e_j$ of the path $P_n$ such that $s \le j \le n-s+1$.

3. The load induced by a set of $k$ non empty independent sets is exactly $k$ on the arc $(\lfloor n/2 \rfloor, \lfloor n/2 \rfloor + 1)$.

**Proof.** Property 3-1 follows from the fact that an independent set $I(\sigma, t)$ loads with load at most 1 each arc and so the load due to $k$ independent sets is at most $k$. Furthermore an independent set $I(\sigma, t)$ with $1 \le \sigma \le s \le n/2$, adds one unit of load on each arc $e_j$ of the path $P_n$ such that $t \le j \le t+\sigma w(\sigma, t)$. But we have $1 \le t \le \sigma \le s$ and $t+\sigma w(\sigma, t) \ge n-\sigma+1 \ge n-s+1$, proving Property 3-2. In particular such an independent set loads with load 1 the arc $(\lfloor n/2 \rfloor, \lfloor n/2 \rfloor + 1)$. An independent set $I(\sigma, t)$ with $\sigma > n/2$ is non empty if $t+\sigma \le n$, so $t < n/2$ and $t+\sigma > n/2$. In that case, this independent set contains exactly one request $(t, t+\sigma)$ which covers the arc $(\lfloor n/2 \rfloor, \lfloor n/2 \rfloor + 1)$, proving Property 3-3. $\square$

**Corollary 4** *The set of requests of $C$ independent sets forms a feasible solution. A feasible solution cannot contain the requests of $C+1$ non empty independent sets.*

**Proof.** The first part follows from Property 3-1 applied with $k = C$. The second part follows from Property 3-3 applied with $k = C+1$ as the load on the arc $(\lfloor n/2 \rfloor, \lfloor n/2 \rfloor + 1)$ will exceed the grooming factor $C$. $\square$

### 3 A non optimal greedy solution and a false conjecture

As said in the Introduction, intuitively one can think that the maximum is obtained by taking the greedy solution consisting of all requests of the smallest length. More precisely

**Definition 5** (Lexicographic order). We can order the independent sets in (increasing) lexicographic order. In this order, an independent set $I(\sigma, t)$ appears before the independent set $I(\sigma', t')$ if $\sigma < \sigma'$, or if $\sigma = \sigma'$ and $t < t'$.

The greedy solution is therefore obtained by taking the first $C$ independent sets in the lexicographic order, which form a feasible solution by Corollary 4. Let $G(C, n)$ be the number of requests in this greedy solution. As mentioned in the preceding section, the greedy solution is optimal for $C \le 6$ and one can prove that it is also the case for $C \le 9$. Hence, it was conjectured that the greedy solution is always optimum. In particular, if $C = C_s = s(s+1)/2$ and $s \le n/2$ the greedy solution will consist exactly of all requests of size $\le s$ and their number is $G(C, n) = sn - C_s$. For $C = 3$, we have $T(3, n) = G(3, n) = 2n - 3$, and for $C = 6$ and $n \ge 6$, we have $T(6, n) = G(6, n) = 3n - 6$.
However, this conjecture is false as can be easily seen from the following example. Let $n = 11$ and $C = 10$ ($s = 4$); then the greedy solution consists of all requests of size $\le 4$ and contains $G(10, 11) = 34$ requests. But a better solution (that we will prove later to be optimal) can be obtained by deleting from the preceding solution the request (4, 8) of size 4 (i.e., remove the independent set $I(4, 4)$ of weight 1) and adding the two requests of size 5 of the independent set $I(5, 1) = \{(1, 6), (6, 11)\}$ of weight 2. Therefore we can groom $T(10, 11) = 35$ requests. One can see that this solution still consists of $C$ independent sets but not the $C$ first in the lexicographic order as the independent set $I(5, 1)$ appears in this solution while the independent set $I(4, 4)$ of the greedy solution does not appear.

Another simple example is given for $s = 6$, $C = C_6 = 21$ and $n = 16$. The greedy solution consists of the $G(21, 16) = 75$ requests of size $\le 6$ (or of the 21 first independent sets $I(\sigma, t)$ in the lexicographic order (with $1 \le t \le \sigma \le 6$). But we can delete from the greedy solution two requests of length 6, namely (5, 11) and (6, 12) (corresponding to the independent sets $I(6, 5)$ and $I(6, 6)$, each of weight 1, and add the 4 requests of length 7, (1, 8), (8, 15), (2, 9) and (9, 16) corresponding to the two independent sets $I(7, 1)$ and $I(7, 2)$ each of weight 2. Therefore we get a better solution with 77 requests. We will see later that this number is optimal and so $T(21, 16) = 77$.

# 4 Existence of an optimal solution consisting of the C independent sets with largest weights

In this section, we consider the MARPG problem from the point of view of the requests that will be satisfied in an optimal solution of the problem. We recall that we suppose $C < \lfloor n^2/4 \rfloor$. The main result is that there exists an optimal solution for the MARPG problem consisting of $C$ independent sets $I(\sigma, t)$ (Theorem 6), which will imply that the solution consisting of the $C$ independent sets with the highest weights is optimal (Theorem 8) and will allow us to compute $T(C, n)$ in Section 5.

**Theorem 6** Let $C < \lfloor n^2/4 \rfloor$ be given. There exists an optimal solution for the MARPG problem consisting of $C$ independent sets $I(\sigma, t)$.

**Proof.** Either there exists an optimal solution consisting of independent sets $I(\sigma, t)$ and we are done as their number is $C$. Indeed, this number cannot be greater than $C$ otherwise by Corollary 4 the solution will not be feasible. Furthermore, it cannot be less than $C$ as $C < \lfloor n^2/4 \rfloor$ implies that some requests are not covered by these independent sets and so at least one request can be added to the solution, contradicting the optimality of the solution.

Otherwise, for any optimal solution $S$, there exists a couple $(\sigma, t)$ such that at least one request of $I(\sigma, t)$ appears in $S$ and another request of $I(\sigma, t)$ does not appear in $S$. Let $(\sigma_0, t_0)$ be the minimum (for the lexicographic order) couple $(\sigma, t)$ in $S$ with this property. Therefore for any $(\sigma, t) < (\sigma_0, t_0)$, either all the requests of $I(\sigma, t)$ appear in $S$ or none of them appear in $S$. Let $C_S$ be the number of independent sets $I(\sigma, t)$, with $(\sigma, t) < (\sigma_0, t_0)$, appearing fully in $S$. We claim that $C_S < C$. Indeed, By Property 3-2 the load of the arcs $e_j$ with $\sigma_0 \le j \le n - \sigma_0 + 1$ is exactly $C_S$. But, as $I(\sigma_0, t_0)$ contains at least two requests, then $\sigma_0 \le n/2$ and the request of $I(\sigma_0, t_0)$ appearing in $S$ covers at least one arc $e_{j_0}$ of the subpath $\sigma_0 \le j \le n - \sigma_0 + 2$. Consequently, the arc $e_{j_0}$ will have a load $C_S + 1$ and as the solution is feasible we have $C_S + 1 \le C$.

Consider now an optimal solution $S_0$ such that $C_{S_0}$ is the greatest possible. From $S_0$ we will build another optimal solution $S'$, containing exactly the same independent sets $I(\sigma, t)$, with $(\sigma, t) < (\sigma_0, t_0)$ as in $S_0$, but such that the independent set $I(s_0, t_0)$ appears fully in $S'$. So, for this solution we will have $C_{S'} > C_{S_0}$ contradicting the maximality of $C_{S_0}$.
From the definition of $(\sigma_0, t_0)$, it follows that there exist in $I(\sigma_0, t_0)$ two consecutive requests, one appearing in $S_0$ denoted $R'_0$ and one not appearing denoted $R_0$. We distinguish two cases.

* Case 1: The request appearing $R'_0$ is before the request not appearing $R_0$. Let $R_0 = (t_0 + j\sigma_0, t_0 + (j+1)\sigma_0)$ and so $R'_0 = (t_0 + (j-1)\sigma_0, t_0 + j\sigma_0)$. Note that $j \ge 1$ and so $t_0 + j\sigma_0 \ge \sigma_0$.

As $S_0$ is optimal, we cannot add the request $R_0$ to $S_0$. Therefore among the arcs covered by the subpath associated to $R_0$, some of them have load $C$. Choose the one with the smallest index and call it $e^*$. It can be written $e^* = e_{t_0+j\sigma_0+i_0} = (t_0 + j\sigma_0 + i_0, t_0 + j\sigma_0 + i_0 + 1)$, with $0 \le i_0 \le \sigma_0 - 1$. Among the $C$ requests covering $e^*$, at most $C_0$ of them belong to the $C_0$ independent sets $I(\sigma, t)$, with $(\sigma, t) < (\sigma_0, t_0)$, appearing fully in $S_0$. Therefore there are $C_1 \ge C - C_0$ requests covering $e^*$ belonging to some $I(\sigma, t)$, with $(\sigma, t) > (\sigma_0, t_0)$.

It is impossible that all these $C_1$ requests start in vertices $< t_0 + j\sigma_0$. Indeed, if it was the case, these $C_1$ requests will cover the arc $(t_0 + j\sigma_0 - 1, t_0 + j\sigma_0)$; but this arc is by Property 3-2 also covered by all the $C_0$ independent sets $I(\sigma, t)$, with $(\sigma, t) < (\sigma_0, t_0)$, appearing fully in $S_0$, and by the request $R'_0$, and so the load of this arc will be strictly greater than $C$.

Therefore, among the $C_1$ requests covering $e^*$ belonging to some $I(\sigma, t)$, with $(\sigma, t) > (\sigma_0, t_0)$, at least one denoted $R_1$ starts in a vertex $i_1 \ge t_0 + j\sigma_0$ and $R_1 = (i_1, i_1 + \sigma_1)$, with $\sigma_1 \ge \sigma_0$. As $\sigma_1 \ge \sigma_0$, the request $R_1$ covers also all the arcs of $R_0$ after $e^*$. Furthermore, by the minimality of $e^*$, the arcs of $R_0$ before $e^*$ have load at most $C-1$. So, if we delete $R_1$, all the arcs of $R_0$ will have a load at most $C-1$ and we can replace $R_1$ by $R_0$ without changing the maximum load $C$ and keeping the requests in $S_0$ of $I(\sigma, t)$, with $(\sigma, t) < (\sigma_0, t_0)$. Therefore we obtain another optimal solution $S_1$ with one request more than $S_0$ in $I(\sigma_0, t_0)$. Repeating the procedure, we eventually obtain an optimal solution $S'$ containing exactly the same requests of $I(\sigma, t)$ with $(\sigma, t) < (\sigma_0, t_0)$, as in $S_0$, and all the requests of the independent set $I(\sigma_0, t_0)$, getting the desired contradiction ($C_{S'} > C_{S_0}$).

* Case 2: The request appearing $R'_0$ is after the request not appearing $R_0$. Let $R_0 = (t_0 + (j-1)\sigma_0, t_0 + j\sigma_0)$ and so $R'_0 = (t_0 + j\sigma_0, t_0 + (j+1)\sigma_0)$. The proof is similar to Case 1. As $S_0$ is optimal, we cannot add the request $R_0$ to $S_0$. Therefore among the arcs covered by the subpath associated to $R_0$, some of them have load $C$. Choose the one with the largest index and call it $f^*$. It can be written $f^* = e_{t_0+(j-1)\sigma_0+i_0}$, with $0 \le i_0 \le \sigma_0 - 1$. Among the $C$ requests covering $f^*$, by Property 3-2 exactly $C_0$ of them belong to the $C_0$ independent sets $I(\sigma, t)$, with $(\sigma, t) < (\sigma_0, t_0)$, appearing fully in $S_0$. Therefore there are $C-C_0$ requests covering $f^*$ belonging to some $I(\sigma, t)$, with $(\sigma, t) > (\sigma_0, t_0)$.

It is impossible that all these $C-C_0$ requests end in vertices $> t_0 + j\sigma_0$. Indeed, if it was the case the arc $(t_0 + j\sigma_0, t_0 + j\sigma_0 + 1)$ will be covered by these $C-C_0$ requests plus the $C_0$ independent sets $I(\sigma, t)$, with $(\sigma, t) < (\sigma_0, t_0)$, appearing fully in $S_0$ (by Property 3-2) and by the request $R'_0$, and so the load of this arc will be strictly greater than $C$.

Therefore, among the $C-C_0$ requests covering $f^*$ belonging to some $I(\sigma, t)$, with $(\sigma, t) > (\sigma_0, t_0)$, at least one denoted $R_1$ ends in a vertex $i_1 \le t_0 + j\sigma_0$ and $R_1 = (i_1 - \sigma_1, i_1)$, with $\sigma_1 \ge \sigma_0$. As $\sigma_1 \ge \sigma_0$, the request $R_1$ covers also all the arcs of $R_0$ before $f^*$. Furthermore, by the maximality of $f^*$, the arcs of $R_0$ after $f^*$ have load at most $C-1$. So, if we delete $R_1$, all the arcs of $R_0$ will have a load at most $C-1$ and we can replace $R_1$ by $R_0$ without changing the maximum load $C$ and keeping the requests in $S_0$ of $I(\sigma, t)$, with $(\sigma, t) < (\sigma_0, t_0)$. Therefore, we obtain another optimal solution $S_1$ with one request more than $S_0$ in $I(\sigma_0, t_0)$. Repeating the procedure, we eventually obtain an optimal solution
$S'$ containing containing exactly the same requests of $I(\sigma, t)$, with $(\sigma, t) < (\sigma_0, t_0)$ as in $S_0$ and all the requests of the independent set $I(\sigma_0, t_0)$, getting the desired contradiction.

☐

**Definition 7 (weight order)** We can also order the independent sets in the “weight order”. In this order an independent set $I(\sigma, t)$ appears before the independent set $I(\sigma', t')$ if it has a larger weight $w(I(\sigma, t)) > w(I(\sigma', t'))$, or if it has the same weight and is lexicographically before it.

**Theorem 8** Given $n$ the size of a directed path and $C$ the grooming factor, the set of the requests included in the $C$ first independent sets in the weight order forms an optimal solution to the MARPG problem.

**Proof.** Let $I_1 \le I_2 \le \dots \le I_C$ be the first $C$ independent sets within the weight order. By Theorem 6, there exists an optimal solution consisting of $C$ independent sets $I_{j_1}, I_{j_2}, \dots, I_{j_C}$. But $w(I_{j_k}) \le w(I_k)$ and so the solution consisting of the $C$ first independent sets in the weight order has a total weight (number of requests) greater than or equal to the weight of this optimal solution and so is optimal.

☐

It is important to understand that the weight order is different from the lexicographic order and so the first $C$ independent sets in the weight order are not composed only with the requests of smallest size. In order to illustrate this statement let us consider the example of Section 3, with $n = 11$, $s = 4$ and $C = 10$. The set of independent sets ranked in the weight order is reported in Table 1.

<table><caption>Table 1: Independent sets ranked in the weight order when $n = 11$, $s = 4$ and $C = 10$.</caption><thead><tr><th>I(σ, t)</th><th>I(1, 1)</th><th>I(2, 1)</th><th>I(2, 2)</th><th>I(3, 1)</th><th>I(3, 2)</th><th>I(3, 3)</th><th>I(4, 1)</th><th>I(4, 2)</th><th>I(4, 3)</th><th>I(5, 1)</th><th>I(4, 4)</th><th>I(5, 2)</th><th>...</th></tr></thead><tbody><tr><td>w<sub>σ,t</sub></td><td>10</td><td>5</td><td>4</td><td>3</td><td>3</td><td>2</td><td>2</td><td>2</td><td>2</td><td>2</td><td>1</td><td>1</td><td>1</td><td></td></tr></tbody></table>

Note that an optimal solution contains the 10 independent sets with weight at least 2 and so we do not take in the optimal solution all the 4 independent sets with $\sigma = 4$. In particular, we do not take the independent set $I(4, 4)$ ranked in position 10 in the lexicographic order but we take $I(5, 1)$ ranked 10 in the weight order as $w(5, 1) = 2$. Therefore we obtain 35 requests for the maximum number of requests that can be satisfied on a path of size 11 with a grooming factor 10. We will say that in that case we have one *anomaly* which corresponds to the independent set $I(5, 1)$.

Remark that Theorem 8 works also for a generalization of the MARPG problem, called Maximal Multiple Request Path Grooming (MMRPG) problem. In the MMRPG problem, we authorize all $I(\sigma, t)$ to appear $\lambda_{\sigma,t}$ times, where $\lambda_{\sigma,t}$ is an integer which can be zero. That is, the set of requests is $\bigcup \lambda_{\sigma,t} R_{\sigma,t}$. Therefore, an optimal solution is obtained by taking the $C$ first admissible independent sets, ordered decreasingly by their weights.

# 5 Anomalies and number of requests of an optimal solution

In what follows we consider two particular feasible solutions each consisting of $C$ independent sets:

* the greedy solution obtained by taking the $C$ first independent sets in the increasing lexicographic (or greedy) order of the tuples $(\sigma, t)$ (see Definition 5). The number of requests in the greedy solution is denoted $G(C, n)$.
* the optimal solution, denoted $S^*$, obtained by taking the $C$ first independent sets in the increasing weight order of the tuples $(\sigma, t)$ (see Definition 7). The number of requests in the optimal solution is denoted $T(C, n)$.

Note that there might exist many optimal solutions (with $T(C, n)$ requests) but in order to ease the computation of $T(C, n)$ we will only consider the optimal solution $S^*$.

**Definition 9** An anomaly is an independent set which appears in the optimal solution $S^*$, where the independent sets are ordered in the weight order, but does not appear in the greedy solution where the independent sets are ranked in lexicographic order. The number of anomalies will be denoted $An(C, n)$.

Equivalently $An(C, n)$ corresponds to the number of independent sets of the greedy solution not appearing in the $C$ first independent sets in the weight order (of the optimal solution $S^*$).

In the example of the preceding section with $n = 11$ and $C = 10$, the set $I(5, 1)$ is an anomaly. It has weight 2 while the set $I(4, 4)$ of the greedy solution not appearing in the optimal solution $S^*$ has weight 1. Similarly in the case $n=16$ and $C = 21$ (see the example at the end of Section 3) the independent sets $I(7, 1)$ and $I(7, 2)$ are anomalies. They have weight 2 while the sets $I(6, 5)$ and $I(6, 6)$ of the greedy solution not appearing in the optimal solution $S^*$ have weight 1.

In the rest of this section we first consider the case $n \le 2s$, where there are no anomalies and give in that case the values $T(C, n) = G(C, n)$ (Theorem 10). Then, in Theorem 11 we compute $G(C, n)$. Finally, in Theorem 12 we compute $An(C, n)$ and prove that each anomaly replaces an independent set of the greedy solution by an independent set with one request more, and so that $T(C, n) = G(C, n) + An(C, n)$.

Let $s$ be defined as the integer such that $C_{s-1} < C \le C_s$, where $C_s = \frac{s(s+1)}{2}$. We first deal with the case $n \le 2s$ where there are no anomalies and so where the computation of $T(C, n) = G(C, n)$ is easy.

**Theorem 10** Let $n$ and $C$ be given. Let $s$ be the integer such that $C_{s-1} < C \le C_s$, where $C_s = \frac{s(s+1)}{2}$. If $n \le 2s$, the number of requests of an optimal solution of the MARPG problem is

* If $C \ge \lfloor \frac{n^2}{4} \rfloor$: $T(C, n) = \frac{n(n-1)}{2}$;

* If $n$ is even and $\frac{n(n-2)}{8} < C \le \lfloor \frac{n^2}{4} \rfloor$: $T(C, n) = \frac{n(n-2)}{4} + C$;

* If $n$ is odd and $\frac{n^2-1}{8} < C \le \lfloor \frac{n^2}{4} \rfloor$: $T(C, n) = \frac{(n-1)^2}{4} + C$.

**Proof.** Let $D(n) = n(n-2)/8$ if $n$ is even and $D(n) = (n^2-1)/8$ if $n$ is odd. Since $n \le 2s$, we first note that we have $C > s(s-1)/2 > D(n)$.

If $C \ge \lfloor \frac{n^2}{4} \rfloor$ we can groom all the requests and so in that case $T(C, n) = \frac{n(n-1)}{2}$.

If $D(n) < C \le \lfloor \frac{n^2}{4} \rfloor$, we note that for a given $\sigma < n/2$ the number of independent sets of $R(\sigma)$ is $\sigma$. So, the number of independent sets of $R$ with $\sigma < n/2$ is $\sum_{\sigma=1}^{\frac{n-2}{2}} \sigma = \frac{n(n-2)}{8}$ if $n$ is even and $\sum_{\sigma=1}^{\frac{n-1}{2}} \sigma = \frac{n^2-1}{8}$ if $n$ is odd, and so exactly $D(n)$.

Furthermore, for any $\sigma \ge n/2$, we have $w(\sigma, t) = 1$. So the $C$ first independent sets in the lexicographic order (of the greedy solution) contain all the $D(n)$ independent sets of $R$ with $\sigma < n/2$ plus $C - D(n)$ independent sets of weight 1. But the $C$ first independent sets in the weight order of the optimal solution $S^*$ also contain the same independent sets and so there are no anomalies.
If $n$ is even the number of requests in the $D(n)$ independent sets of $R$ with $\sigma < n/2$ is (as the number of requests of size $\sigma$ is $n - \sigma$) $\sum_{\sigma=1}^{\frac{n-2}{2}}(n - \sigma) = \frac{3n(n-2)}{8}$. Then we add $C - \frac{n(n-2)}{8}$ independent sets with weight 1 and so the total number of requests is

$$T(C, n) = G(C, n) = \frac{3n(n-2)}{8} + C - \frac{n(n-2)}{8} = \frac{n(n-2)}{4} + C$$

If $n$ is odd, the number of requests in the $D(n)$ independent sets of $R$ with $\sigma < n/2$ is $\sum_{\sigma=1}^{\frac{n-1}{2}}(n - \sigma) = \frac{(n-1)(3n-1)}{8}$. Then we add $C - \frac{n^2-1}{8}$ independent sets with weight 1 and so the number of requests is

$$T(C, n) = G(C, n) = \frac{(n-1)(3n-1)}{8} + C - \frac{n^2-1}{8} = \frac{(n-1)^2}{4} + C$$

□

Now we deal with the interesting case $n > 2s$, where there might be anomalies. We first compute the number $G(C, n)$ of requests in the greedy solution.

**Theorem 11** Let $n$ and $C$ be given. Let $s$ be the integer such that $C_{s-1} < C \le C_s$, where $C_s = \frac{s(s+1)}{2}$. Let $d = C_s - C$ and let $s \ge 1$ and $n \ge 2s$. Let $q$ and $r$ be such that $n = q_s + r$, where $0 \le r \le s - 1$. Then, the number of requests in the greedy solution is:

$$G(C, n) = sn - s(s + 1)/2 - dq + \min\{d, s - r\}$$

**Proof.** We note that the requests of the greedy solution are all the requests of the independent sets $R(\sigma)$ with $\sigma \le s - 1$ in number $(s - 1)n - s(s - 1)/2$, plus those of the first $s - d$ independent sets of $R(s)$ (in the lexicographic order). We also note that, by the definition of $r$, the first $r$ independent sets of $R(s)$ have weight $q$, while the $s - r$ last ones have weight $q - 1$. So we have to distinguish two cases

* Case 1: $d \le s - r$ or $r \le s - d$:

In that case, among the first $s - d$ independent sets of $R(s)$ in the greedy solution, $r$ of them have weight $q$ and $s - d - r$ weight $q - 1$. So the number of requests of the greedy solution with size $s$ is $qr + (q - 1)(s - d - r) = q_s + r - s - (q - 1)d = n - s - (q - 1)d$. Therefore

$$G(C, n) = sn - s(s + 1)/2 - (q - 1)d$$

* Case 2: $d \ge s - r$ or $r \ge s - d$:

In that case all the first $s - d$ independent sets of $R(s)$ in the greedy solution have weight $q$ and the number of requests in these independent sets is $q(s - d) = n - r - q_d$ and so

$$G(C, n) = sn - s(s + 1)/2 - q_d + s - r$$

We can summarize the results of the two cases with the formula of the theorem.

We note that when $C = C_s$ ($d = 0$), then $T(C_s, n) = sn - s(s + 1)/2$ (which is the number of requests of length at most $s$). □

**Theorem 12** Let $n$ and $C$ be given. Let $s$ be the integer such that $C_{s-1} < C \le C_s$, where $C_s = \frac{s(s+1)}{2}$. Let $d = C_s - C$ and let $s \ge 1$ and $n \ge 2s$. Let $q$ and $r$ be such that $n = q_s + r$,
where $0 \le r \le s - 1$. Let $r = aq + \alpha$, where $0 \le \alpha \le q - 1$ and $s - r = b(q + 1) + \beta$, where $0 \le \beta \le q$. Finally, let

$$A(C, n) = ar - \frac{a(a + 1)}{2}q = \frac{r^2 - qr + \alpha(q - \alpha)}{2q},$$

$$B(C, n) = (b+1)(s-r) - \frac{b(b+1)}{2}(q+1) = \frac{(s-r)^2 + (q+1)(s-r) + \beta(q+1-\beta)}{2(q+1)}.$$

Then, the number of anomalies is:

$$\begin{aligned} An(C, n) &= \min\{A(C, n), B(C, n) - d\} + \max\{0, r + d - s\} \\ &= \min\{A(C, n) + d, B(C, n)\} - \min\{d, s - r\} \end{aligned}$$

and the number of requests of an optimal solution to the MARPG problem when $n \ge 2s$ is

$$T(C, n) = G(C, n) + An(C, n) = sn - s(s + 1)/2 - dq + \min\{A(C, n) + d, B(C, n)\}$$

**Proof.** We first note the two following properties:

- Property A: the independent sets of $R$ with $\sigma \le s$ have weight $\ge q - 1$. Indeed, as $t \le s$, we have $w(\sigma, t) = \lfloor \frac{n-t}{\sigma} \rfloor \ge \lfloor \frac{n-t}{s} \rfloor \ge \lfloor \frac{(q-1)s+s-t+r}{s} \rfloor \ge q - 1$.

- Property B: the independent sets of $R$ with $\sigma \ge s$ have weight $\le q$. Indeed, as $r \le s - 1$, we have $w(\sigma, t) = \lfloor \frac{n-t}{\sigma} \rfloor \le \lfloor \frac{n-t}{s} \rfloor \le \lfloor \frac{(q+1)s-1-t}{s} \rfloor \le q$.

Let us consider the following sets ranked in the weight order:

- type (0): the independent sets with weight $\ge q + 1$;

- type (1): the independent sets of the greedy solution (that is among the $C$ first independent sets in the greedy order) with weight $q$;

- type (2): the independent sets not in the greedy solution with weight $q$, and let $A'(C, n)$ be their number;

- type (3): the independent sets of the greedy solution with weight $q - 1$, and let $B'(C, n)$ be their number.

We note that by Property B the sets of type (0) satisfy $\sigma < s$. Consequently, their number is less than or equal to $s(s-1)/2$ and strictly less than $C$. Hence they are all both in the greedy solution and in the optimal solution $S^*$. By definition the sets of type (1) are all in the greedy solution and also in the optimal solution $S^*$ (as the number of sets of type (0) and (1) is at most $C$). We also note that by Property A the sets with weight $\le q - 2$ satisfy $\sigma > s$ and so they are ranked after rank $s(s+1)/2 \ge C$. So, they do not appear either in the greedy solution or in the optimal solution $S^*$.

Therefore the greedy solution consists of all the $C$ independent sets of type (0), (1) and (3). The optimal solution $S^*$ consists of all the independent sets of type (0) and (1), plus if $B'(C, n) > 0$ some independent sets of type (2) and then if $A'(C, n) < B'(C, n)$ some independent sets of type (3). Therefore, the anomalies are exactly the independent sets of type (2) which are in the optimal solution $S^*$. If $A'(C, n) \le B'(C, n)$, then all the independent sets of type (2) appear in the $C$ first independent sets of the optimal solution $S^*$ and then $An(C, n) = A'(C, n)$. If $A'(C, n) \ge B'(C, n)$, then only $B'(C, n)$ independent sets of type (2) appear in the $C$ first independent sets of type (0).
independent sets of the optimal solution $S^*$ and then $An(C, n) = B'(C, n)$ (equivalently in that case all the $B'(C, n)$ independent sets of type (3) are not in the optimal solution $S^*$). In summary, we have

$$An(C, n) = \min\{A'(C, n), B'(C, n)\}$$

Furthermore, we note that the optimal solution $S^*$ is obtained from the greedy solution by replacing $An(C, n)$ independent sets of size $q-1$ with $An(C, n)$ independent sets of size $q$ and so

$$T(C, n) = G(C, n) + An(C, n)$$

To compute $A'(C, n)$ we split the independent sets of type (2) into two parts, those with $\sigma > s$ which are not in the greedy solution (as they are ranked after rank $s(s+1)/2 \ge C$) and those with $\sigma = s$. Let $A(C, n)$ be the number of independent sets of $R$ with $\sigma > s$ and weight $q$. As $r = aq + \alpha$, there are, for $1 \le k \le a$, $r - kq$ independent sets of weight $q$ in $R(s+k)$ and so altogether

$$A(C, n) = \sum_{k=1}^{k=a} (r - kq) = ar - \frac{a(a+1)}{2}q = \frac{r^2 - qr + \alpha(q - \alpha)}{2q}$$

We now compute the number of independent sets of $R$ with $\sigma = s$ and weight $q$. As seen in the proof of Theorem 11, $r$ of them are in the greedy solution. So, if $r \le s-d$, the independent sets of type (2) are all in the greedy solution and so in that case $A'(C, n) = A(C, n)$.

If $r \ge s-d$, we have $r - (s-d)$ independent sets with $\sigma = s$ not in the greedy solution and so of type (2). Consequently, in that case, we have $A'(C, n) = A(C, n) + r - (s-d)$.

In summary,

$$A'(C, n) = A(C, n) + \max\{0, (r + d - s)\} = A(C, n) + d - \min\{d, s - r\}$$

Let $B(C, n)$ be the number of independent sets of $R$ with $\sigma \le s$ and weight $q-1$. As $s-r = b(q+1) + \beta$, for $0 \le h \le b$, there are $s-r-h(q+1)$ independent sets of weight $q-1$ in $R(s-h)$. So, altogether we have

$$B(C, n) = \sum_{h=0}^{h=b} (s - r - h(q + 1)) = (b + 1)(s - r) - \frac{b(b + 1)}{2}(q + 1)$$

Using $b(q+1) = s-r-\beta$, with $0 \le \beta \le q$, we get:

$$B(C, n) = \frac{(s-r)^2 + (q+1)(s-r) + \beta(q+1-\beta)}{2(q+1)}$$

We can now express $B'(C, n)$ in function of $B(C, n)$. If $r \le s-d$, then $d$ of them are not of type (3) and so in that case $B'(C, n) = B(C, n) - d$. If $r \ge s-d$, then $s-r$ of them are not of type (3) and so in that case $B'(C, n) = B(C, n) - (s-r)$. In summary,

$$B'(C, n) = B(C, n) - \min\{d, s-r\} = B(C, n) - d + \max\{0, (r-s) + d\}$$

In summary, we get the formula of the theorem for the number of anomalies $An(C, n)$ and for the maximum number of requests $T(C, n)$ using $T(C, n) = G(C, n) + An(C, n)$. $\square$

**Corollary 13** When $C = C_s = s(s+1)/2$, and so $d = 0$, we have

$$An(C_s, n) = \min\{A(C_s, n), B(C_s, n)\} \text{ and } T(C_s, n) = sn - C_s + \min\{A(C_s, n), B(C_s, n)\}$$
**Corollary 14** When $q \ge s-1$ (or $n \ge s(s-1)$) then there are no anomalies.

**Proof.** If $q \ge s-1$ we have $r \le q$ and so $A(C,n) = 0$ and $A'(C,n) = 0$ when $r \le s-d$. We also have $s-r \le q+1$ and so $B(C,n) \le s-r$ and $B'(C,n) = 0$ when $r \ge s-d$. $\square$

We show in Figure 1 the exact number of anomalies for grooming factor $C = 192$, an effective value for Synchronous Optical Networking (SONET), and in Figure 2 the number of anomalies for grooming factor $C = 256$, an effective value for the Synchronous Digital Hierarchy (SDH). See for instance [8] for more details on SONET/SDH. We have also reported the upper bounds $[M^*(C, q)]$ and $[UB(C, q)]$ on the number of anomalies given in Theorems 16 and 17 (Section 6). We observe that for each value of $q$ (indicated in the figures on top of each segment), the bounds are close to the maximum number of anomalies and that this maximum value is regularly reached.

<figure><img src="image_1.png" /><figcaption>Figure 1: Number of anomalies for grooming factor $C = 192$.</figcaption></figure>

<figure><img src="image_2.png" /><figcaption>Figure 2: Number of anomalies for grooming factor $C = 256$.</figcaption></figure>
## 6 Bounds on the maximum number of anomalies $An^*(C)$

As noted in the preceding section, there are no anomalies if $n \le 2s$ (Theorem 10) or $n \ge s(s-1)$ (Corollary 14). So in this section we assume that $2s < n < s(s-1)$ and, as $n = qs + r$, we also assume that $2 \le q \le s-2$.

We want to determine, for a given $C$, the maximum number (or at least a tight upper-bound) of the number of anomalies $An^*(C)$ for $2s < n < s(s-1)$ that is

$$An^*(C) = \max_{2s < n < s(s-1)} An(C, n)$$

We will also give an upper-bound when the value $q$ is fixed, that is when $qs \le n < (q+1)s$

$$An^*(C, q) = \max_{qs \le n < (q+1)s} An(C, n) \quad \text{where} \quad 2 \le q \le s-2.$$

Recall that $n = qs + r$, with $0 \le r \le s-1$. Let $r = aq + \alpha$, with $0 \le \alpha \le q-1$, and let $s-r = b(q+1) + \beta$, with $0 \le \beta \le q$.

Recall that the number of anomalies is

$$An(C, n) = \min\{A(C, n), B(C, n) - d\} + \max\{0, r + d - s\}$$

As $q$ and $r$ play an important role, we will emphasize them in the notation.

$$A(C, n) = A(s, r, q) = ar - \frac{a(a+1)}{2}q = \frac{r^2 - qr + \alpha(q - \alpha)}{2q}$$ $$B(C, n) = B(s, r, q) = (b+1)(s-r) - \frac{b(b+1)}{2}(q+1) = \frac{(s-r)^2 + (q+1)(s-r) + \beta(q+1-\beta)}{2(q+1)}$$

**Theorem 15** Let $2s < n < s(s-1)$; $C_s = s(s+1)/2$; $C = C_s - d$ with $0 \le d \le s-1$ and $d_0 = (s+1/2)^2/2(q+1)$. We have

$$An^*(C, q) \le M^*(C, q)$$

where

**Case 1:** If $d \ge d_0$,

$$M^*(C, q) = d + (q+1)/2 - \sqrt{2(q+1)d} = \left(\sqrt{d} - \sqrt{(q+1)/2}\right)^2$$

**Case 2:** If $d < d_0$,

$$M^*(C, q) = \left[ \sqrt{(q+1)(C+1/8)} - \sqrt{q(C_s + 1/8)} \right]^2 + \max \left\{ 0, \sqrt{2q(q+1)(C+1/8)} + d - (q+1)s \right\}$$

**Proof.** Let $r = aq + \alpha$, with $0 \le \alpha \le q-1$. We first prove that, for $r \le s-2$, we have:

$$A(s, r+1, q) - A(s, r, q) = a$$
Indeed that is immediate if $\alpha < q - 1$, as $r + 1 = aq + \alpha + 1$. If $\alpha = q - 1$, and so $r = aq + q - 1$, we have $r + 1 = (a + 1)q$ and so $A(s, r + 1, q) = (a + 1)^2q - (a + 1)(a + 2)q/2 = a(a + 1)q/2$, while $A(s, r, q) = a(aq + q - 1) - a(a + 1)q/2 = a(a + 1)q/2 - a$.

In summary, the function $A(s, r, q)$ is increasing in $r$ and so the function $A'(C, n) = A(s, r, q) + \max\{0, r + d - s\}$ is also increasing in $r$.

Similarly let us prove that if $s - (r + 1) = b(q + 1) + \beta$, then

$$B(s, r, q) - B(s, r + 1, q) = b + 1$$

If $\beta < q$ the $b$ in $B(s, r, q)$ and $B(s, r + 1, q)$ are the same and so $B(s, r, q) - B(s, r + 1, q) = (b + 1)[s - r - (s - (r + 1)] = b + 1$.

If $\beta = q$, then we have $s - (r + 1) = b(q + 1) + q$ and $s - r = (b + 1)(q + 1)$. So, $B(s, r, q) = (b + 1)^2(q + 1) - b(b + 1)(q + 1)/2 = (b + 2)(b + 1)(q + 1)/2$, while $B(s, r + 1, q) = (b + 1)(b(q + 1) + q) - b(b + 1)(q + 1)/2 = b(b + 1)(q + 1)/2 + (b + 1)q$. So, $B(s, r, q) - B(s, r + 1, q) = b + 1$.

In summary, the function $B(s, r, q) - d$ is strictly decreasing by at least 1 and so the function $B'(C, n) = B(s, r, q) - d + \max\{0, r + d - s\}$ is also decreasing as $\max\{0, r + 1 + d - s\} \le \max\{0, r + d - s\} + 1$.

Let $r(C, q)$ be the greatest integer such that $A(s, r, q) \le B(s, r, q) - d$, or equivalently $A(s, r, q) + \max\{0, r + d - s\} \le B(s, r, q) - d + \max\{0, r + d - s\}$. Then the maximum is attained either for $r(C, q)$ or $r(C, q) + 1$. Indeed, for an integer $r \le r(C, q)$, we have $A(s, r, q) + \max\{0, r + d - s\} \le A(s, r(C, q), q) + \max\{0, r(C, q) + d - s\} = An(C, n = qs + r(C, q))$. Then, for an integer $r \ge r(C, q) + 1$, we have $B(s, r, q) - d + \max\{0, r + d - s\} \le B(s, r(C, q) + 1, q) - d + \max\{0, r(C, q) + 1 + d - s\} = An(C, n = qs + r(C, q) + 1)$. So,

$$An^*(C, q) = \max\{A(s, r(C, q), q) + \max\{0, r(C, q) + d - s\}; \\ B(s, r(C, q) + 1, q) - d + \max\{0, r(C, q) + 1 + d - s\}\}$$

However, the determination of $r(C, q)$ as a function of $s$ is not easy as we deal with integers. So, we will use the trick of working with real numbers. By extension, we let for any real $x = aq + \alpha$ with $0 \le \alpha < q$ and $s - x = b(q + 1) + \beta$ where $0 \le \beta < q + 1$:

$$A(s, x, q) = ax - \frac{a(a + 1)}{2}q = \frac{x^2 - qx + \alpha(q - \alpha)}{2q} \\ B(s, x, q) = (b + 1)(s - x) - \frac{b(b + 1)}{2}(q + 1) = \frac{(s - x)^2 + (q + 1)(s - x) + \beta(q + 1 - \beta)}{2(q + 1)}$$

Similarly as above, one can prove that if $r = aq + \alpha$ and $s - (r + 1) = b(q + 1) + \beta$, then, for $x = r + \lambda$, with $0 \le \lambda \le 1$, we have $A(s, x, q) - A(s, r, q) = \lambda a$ and $B(s, x, q) - B(s, r + 1, q) = (1 - \lambda)(b + 1)$.

Now, let $\rho(C, q)$ be the real number such that $A(s, \rho(C, q), q) = B(s, \rho(C, q), q) - d$, or equivalently, $A(s, \rho(C, q), q) + \max\{0, \rho(C, q) + d - s\} = B(s, \rho(C, q), q) - d + \max\{0, \rho(C, q) + d - s\}$. Let

$$M(C, q) = A(s, \rho(C, q), q) + \max\{0, \rho(C, q) + d - s\} \\ = B(s, \rho(C, q), q) - d + \max\{0, \rho(C, q) + d - s\}$$

We have $r(C, q) \le \rho(C, q) < r(C, q) + 1$. As $A(s, x, q) + \max\{0, x + d - s\}$ is increasing, we have $A(s, r(C, q), q) + \max\{0, r(C, q) + d - s\} \le A(s, \rho(C, q), q) + \max\{0, \rho(C, q) + d - s\} = M(C, q)$. Furthermore, as $B(s, r, q) - d + \max\{0, r + d - s\}$ is decreasing, we also have $B(s, r(C, q) +
$1, q) - d + \max\{0, r(C, q) + 1 + d - s\} \le B(s, \rho(C, q), q) - d + \max\{0, \rho(C, q) + d - s\} = M(C, q)$.
Consequently, we have

$$An^*(C, q) \le M(C, q)$$

The determination of $\rho(C, q)$ is not easy as the $\alpha$ and $\beta$ are varying. We first note that, if $x < q$, then $x = \alpha$ and $A(s, x, q) = 0$. Furthermore, as $0 \le \alpha < q$, we have $0 \le \alpha(q - \alpha) \le q^2/4$, and as $0 \le \beta < q + 1$, we also have $\beta(q + 1 - \beta) \le (q + 1)^2/4$. Let us define for a real number $x$ the functions:

$$ 
\begin{aligned}
\tilde{A}(s, x, q) &= \begin{cases} 0 & \text{if } x \le q/2 \\ (x^2 - qx + q^2/4) / 2q = (x - q/2)^2 / 2q & \text{if } x > q/2 \end{cases} \\
\tilde{B}(s, x, q) &= ((s-x)^2 + (q+1)(s-x) + (q+1)^2/4) / 2(q+1) \\
&= (s - x + (q+1)/2)^2 / 2(q+1)
\end{aligned}
$$

We note that the function $\tilde{A}(s, x, q)$ is increasing and that $A(s, x, q) \le \tilde{A}(s, x, q)$. Similarly $\tilde{B}(s, x, q)$ is decreasing and $B(s, x, q) \le \tilde{B}(s, x, q)$. Let $x(C, q)$ be the real number for which $\tilde{A}(s, x(C, q), q) = \tilde{B}(s, x(C, q), q) - d$ and let

$$ 
\begin{aligned}
M^*(C, q) &= \tilde{A}(s, x(C, q), q) + \max\{0, x(C, q) + d - s\} \\
&= \tilde{B}(s, x(C, q), q) - d + \max\{0, x(C, q) + d - s\}
\end{aligned}
$$

Then $M(C, q) \le M^*(C, q)$ and so $An^*(C, q) \le M^*(C, q)$.

Now let us compute $x(C, q)$ and $M^*(C, q)$ as functions of $C$ and $q$.

Let $x_0$ be the value for which $B(s, x_0, q) - d = 0$. We have $(s - x_0 + (q+1)/2)^2 = 2(q+1)d$ and so $s - x_0 = -(q+1)/2 + \sqrt{2(q+1)d}$ and

$$x_0 = s + (q + 1)/2 - \sqrt{2(q + 1)d}$$

Let $d_0$ be the value for which $x_0 = q/2$, that is $s+1/2 = \sqrt{2(q+1)d_0}$ or $d_0 = (s+1/2)^2/2(q+1)$.

We distinguish two cases according $x_0 \le q/2$ ($d \ge d_0$) or $x_0 > q/2$ ($d \le d_0$).

* Case 1: if $x_0 \le q/2$ or $d \ge d_0 = (s+1/2)^2/2(q+1)$, then we have $\tilde{A}(s, x_0, q) = 0$, and so $x(C, q) = x_0$ and $M^*(C, q) = \max\{0, x_0 + d - s\}$. Observe that:

$$x_0 + d - s = d + (q + 1)/2 - \sqrt{2(q + 1)d} = (\sqrt{d} - \sqrt{(q + 1)/2})^2 \ge 0.$$

$$M^*(C, q) = d + (q + 1)/2 - \sqrt{2(q + 1)d} = (\sqrt{d} - \sqrt{(q + 1)/2})^2$$

* Case 2: if $x_0 > q/2$ or $d < d_0 = (s+1/2)^2/2(q+1)$, then

$$\tilde{A}(s, x(C, q), q) = \tilde{B}(s, x(C, q), q) - d > 0.$$

We get

$$ (q + 1) [x(C, q)^2 - qx(C, q) + q^2/4] = q [(s - x(C, q))^2 + (q + 1)(s - x(C, q)) + (q + 1)^2/4] - 2q(q + 1)d $$
and so $x(C, q)^2 + 2qsx(C, q) - [qs^2 + q(q+1)s + q(q+1)/4 - 2q(q+1)d] = 0$.

Using $s^2 + s = 2(C + d)$, we get

$$ 
\begin{aligned}
x(C, q) &= -qs + \sqrt{q(q+1)(s^2 + s) + q(q+1)/4 - 2q(q+1)d} \\
&= -qs + \sqrt{2q(q+1)(C + 1/8)}
\end{aligned}
$$

Plugging this value in $\tilde{A}(s, x(C, q), q) = [(x - q/2)^2]/2q$ and noting that

$x(C, q) - q/2 = -q(s + 1/2) + \sqrt{2q(q + 1)(C + 1/8)}$ and $s + 1/2 = \sqrt{2(C_s + 1/8)}$, we get:

$$ \tilde{A}(s, x(C, q), q) = \left[ \sqrt{(q+1)(C+1/8)} - \sqrt{q(C_s + 1/8)} \right]^2 $$

and so

$$ M^*(C, q) = \left[ \sqrt{(q+1)(C+1/8)} - \sqrt{q(C_s + 1/8)} \right]^2 + \max\{0, \sqrt{2q(q+1)(C+1/8)} + d - (q+1)s \} $$

□

**Proof of the upper bound for $M^*(C, q)$**

**Theorem 16** Under the hypothesis of Theorem 15.

Case 1: If $d > d_0$, then:

$$ M^*(C, q) \leq UB(C, q) = (2q + 1 - 2\sqrt{q(q+1)}) C = (\sqrt{q+1} - \sqrt{q})^2 C $$

Case 2: If $d < d_0$, then:

$$ M^*(C, q) \leq UB(C, q) = (2q + 1 - 2\sqrt{q(q+1)}) (C + 1/8) = (\sqrt{q+1} - \sqrt{q})^2 (C + 1/8) $$

**Proof.** Let $Q = \sqrt{q(q+1)}$. We prove the result according to the two cases $d \geq d_0$ or $d < d_0$.

* Case 1: $d \geq d_0 = (s + 1/2)^2/2(q + 1)$.

We will prove that $M^*(C, q) = (\sqrt{d} - \sqrt{(q+1)/2})^2 \leq (\sqrt{q+1} - \sqrt{q})^2 C$. As $\sqrt{d}$ is increasing in $d$ and $C$ is decreasing in $d$ from $C_s$ to $C_{s-1} + 1$, it suffices to prove that $(\sqrt{s-1} - \sqrt{(q+1)/2})^2 \leq (\sqrt{q+1} - \sqrt{q})^2 (C_{s-1} + 1)$. Since $q + 1 \leq s - 1$, we can remove the squares and so we have to prove that

$$ \sqrt{s-1} - \sqrt{(q+1)/2} \leq (\sqrt{q+1} - \sqrt{q})\sqrt{(C_{s-1} + 1)} $$

But $C_{s-1} + 1 = (s^2 - s + 2)/2 = (s - 1)^2/2 + (s + 1)/2 \geq (s - 1)^2/2$ and $(\sqrt{q+1} - \sqrt{q}) \geq 1/2\sqrt{q+1}$. Hence the inequality is true if

$$ \sqrt{s-1} - \sqrt{(q+1)/2} \leq (s-1)/2\sqrt{2(q+1)} $$

Let $q + 1 = \alpha(s - 1)$ with $0 < \alpha \leq 1$. We have to prove that

$$ 1 - \sqrt{\alpha/2} \leq 1/2\sqrt{2\alpha} \quad \text{or} \quad 2\sqrt{2\alpha} - 2\alpha \leq 1 $$

which is true since

$$ 1 + 2\alpha - 2\sqrt{2\alpha} = (\sqrt{2\alpha} - 1)^2 \geq 0 $$
• Case 2: $d < d_0 = (s + 1/2)^2/2(q + 1)$.

We will prove that $M^*(C, q) \le UB(C, q) = (2q + 1 - 2Q)(C + 1/8)$.

To simplify the writing we will use the following notations:

$$ \Gamma_s = 2(C_s + 1/8) = (s + 1/2)^2 $$

$$ \Gamma = 2(C + 1/8) = \Gamma_s - 2d = (s + 1/2)^2 - 2d $$

Recall that, when $d < d_0$, we have

$$ M^*(C, q) = \left[ \sqrt{(q+1)\Gamma/2} - \sqrt{q\Gamma_s/2} \right]^2 + \max \left\{ 0, Q\sqrt{\Gamma} + d - (q+1)s \right\} $$

Let us first study the behavior in the interval $[0, s]$ of the function of $d$ implied in the max

$$ \phi(d) = Q\sqrt{\Gamma} + d - (q + 1)s $$

The derivative is $\phi'(d) = 1 - Q/\sqrt{\Gamma}$. We have $\phi'(d) > 0$ as $\sqrt{\Gamma} \ge s - 1/2 \ge Q = \sqrt{q(q+1)}$ as $s \ge q + 1$. So the function is increasing in $d$ and we have $f(0) < 0$ while $f(s) > 0$. So there exists a $d_1$ such that $\phi(d_1) = 0$.

As $C \le C_s$ and $[\sqrt{q+1} - \sqrt{q}]^2 = 2q + 1 - 2\sqrt{q(q+1)}$, we get:

$$ \left[ \sqrt{(q+1)\Gamma/2} - \sqrt{q\Gamma_s/2} \right]^2 \le \left[ \sqrt{q+1} - \sqrt{q} \right]^2 \Gamma/2 = UB(C, q) $$

Therefore, if $d \le d_1$, the max being 0, we have $M^*(C, q) \le UB(C, q)$.

If $d \ge d_1$ the proof is more involved. We have to show that:

$$ \psi(d) = UB(C, q) - M^*(C, q) = Q(\sqrt{\Gamma_s} - 1)\sqrt{\Gamma} - Q\Gamma - (q+1)d + (q+1)s \ge 0 $$

The derivative is $\psi'(d) = -Q(\sqrt{\Gamma_s} - 1)/\sqrt{\Gamma} + 2Q - (q + 1)$. Furthermore, the second derivative $\psi''(d) = -Q(\sqrt{\Gamma_s} - 1)/(\Gamma)^{3/2}$ is negative, and so $\psi'(d)$ is decreasing. For $d = s$, we have $\psi'(s) = Q - (q + 1) < 0$. For $d = 0$, $\psi'(0)$ can be negative or positive according the value of $q$ compared to $s$. So we have two possible behaviors of $\psi(d)$, always decreasing or increasing till some $d_2$ and then decreasing. But $\psi(s) = 0$ and $\psi(0) = (q+1)s - Q(s+1/2) > 0$ as $(q+1)^2s^2 - Q^2(s+1/2)^2 = (q+1)s^2 - q(q+1)(s+1/4) > 0$ as $s \ge q + 1$. So $\psi(d) \ge 0$ on the interval $[0, s]$.

□

Note that when $d = 0$, we have $M^*(C_s, q) = UB(C_s, q)$. Now we will show that in the case $q = 2$, we can slightly improve the bounds of $M^*(C, 2)$ and $UB(C, 2)$.

**Theorem 17** Let $C_s = s(s+1)/2$, $C = C_s - d$ with $0 \le d \le s - 1$, and $2s < n < 3s$. Then

$$ \text{An}^*(C, 2) \le M^*(C, 2) \quad \text{where} $$

$$ M^*(C, 2) = 5C + 2d + 1/2 - \sqrt{2C_s + 1/4}\sqrt{12C + 1} + \max\{0, \sqrt{12C + 1} + d - 3s\}. $$

$$ \text{Furthermore, } M^*(C, 2) \le UB(C, 2) = (5 - 2\sqrt{6})C. $$
**Proof.**

In the case $q = 2$, we can slightly improve the bound in case 2. Indeed, the upper-bound of $\beta(1 - \beta)$ in $\tilde{B}(s, x, q)$ with $(q + 1)^2/4 = 9/4$ can be improved to 2 as $\beta = 0, 1$, or 2. So, in the case $q = 2$ we have

$$ 
\begin{aligned}
\tilde{A}(s, x, 2) &= [x^2 - 2x + 1]/4; \\
\tilde{B}(s, x, 2) &= [(s - x)^2 + 3(s - x) + 2]/6.
\end{aligned}
$$

We get now $x(C, 2) = -2s + \sqrt{12C + 1}$ and $\tilde{A}(s, x(C, 2), 2) = 5C + 2d + 1/2 - \sqrt{2C_s + 1/4}\sqrt{12C + 1}$.

So, we get the value of $M^*(C, 2)$ given in the theorem. With these new values we will prove that now $M^*(C, 2) < (5 - 2\sqrt{6})C$. But first we will prove that for $0 \le d \le s$:

$$ (5 - 2\sqrt{6})C - \tilde{A}(s, x(C, 2), 2) = \sqrt{2C_s + 1/4}\sqrt{12C + 1} - 2\sqrt{6}C - 2d - 1/2 = \phi_2(d) > 0 $$

By taking the squares we have to prove that:

$$ 
\begin{aligned}
& (2C + 2d + 1/4)(12C + 1) \ge (2\sqrt{6}C + 2d + 1/2)^2 \\
\text{or} \\
& 24C^2 + (24d + 5)C + 2d + 1/4 > 24C^2 + 4d^2 + 2d + 1/4 + (8d + 2)\sqrt{6}C \\
\text{or} \\
& (24 - 8\sqrt{6})dC + (5 - 2\sqrt{6})C - 4d^2 \ge 0
\end{aligned}
$$

which is true as $5 - 2\sqrt{6} > 0.1$ and $(24 - 8\sqrt{6})C > 4C > 4d$.

Like above, the function $g(d) = x(C, 2) + d - s = \sqrt{12C + 1} - 3s + d$ is increasing in $d$ with $g(0) < 0$ while $g(s) > 0$. So, there exists a $d_3$ such that $g(d_3) = 0$.

If $d \le d_3$, then we have $(5 - 2\sqrt{6})C - M^*(C, 2) = \phi_2(d) > 0$.

If $d \ge d_3$, then we have

$$ (5 - 2\sqrt{6})C - M^*(C, 2) = \psi_2(d) = (\sqrt{2C_s + 1/4} - 1)\sqrt{12C + 1} - 2\sqrt{6}C + 3s - 3d - 1/2 $$

The derivative is $\psi_2'(d) = -6(\sqrt{2C_s + 1/4} - 1)/\sqrt{12C + 1} + 2\sqrt{6} - 3$. Furthermore, the second derivative $\psi_2''(d)$ is negative. So $\psi_2'(d)$ is decreasing.

Let us prove that for $d = s$, we have $\psi_2'(s) < 0$. Indeed $\sqrt{2C_s + 1/4} - 1 = s - 1/2$ and $\sqrt{12C + 1} = \sqrt{6(s - 1/2)^2 - 1} < \sqrt{6}(s - 1/2)$. So we have to prove that $6(s - 1/2) > (2\sqrt{6} - 3)\sqrt{6}(s - 1/2)$ which is true as $3\sqrt{6} > 6$. For $d = d_3$, $\psi_2'(0)$ can be negative or positive according the value of $q$ compared to $s$. So we have two possible behaviors of $\psi_2(d)$ : always decreasing or increasing till some $d_2$ and then decreasing. But $\psi_2(d_3) = \phi_2(d_3) > 0$ and let us prove that $\psi_2(s) > 0$. That proves that $\psi_2(d) > 0$ on the interval $[d_3, s]$ and concludes the proof.

For $d = s$, we have $\sqrt{2C_s + 1/4} - 1 = s - 1/2 = \sqrt{2C + 1/4}$, and so:

$$ \psi_2(s) = \sqrt{2C + 1/4}\sqrt{12C + 1} - 2\sqrt{6}C - 1/2 $$

So we have to prove by taking the squares that

$$ (2C + 1/4)(12C + 1) \ge 24C^2 + 2\sqrt{6}C + 1/4 \quad \text{or} \quad 5C \ge 2\sqrt{6}C $$

which is true as $5 > 2\sqrt{6}$.

□

**Theorem 18**

$$ An^*(C) = \max_{n \ge 2s} An(C, n) \le (5 - 2\sqrt{6})C $$
**Proof.** If $q = 2$ that is Theorem 17. If $q > 2$, $M^*(C, q) \le (2q + 1 - 2\sqrt{q(q+1)})(C + 1/8)$ by Theorem 15. As the function $2q + 1 - 2\sqrt{q(q+1)}$ is decreasing, we get : $M^*(C, q) \le (7 - 4\sqrt{3})(C + 1/8) < (5 - 2\sqrt{6})C$ as $(7 - 4\sqrt{3})/8 < 0.009 < 0.029C < (4\sqrt{3} - 2\sqrt{6} - 2)C$. $\square$

From the above results, we get the following upper bound on $T(C, n)$.

**Theorem 19** Let $n$ and $C$ be fixed positive integers. Let $s$ be an integer such that $C_{s-1} < C \le C_s$ with $C_s = \frac{s(s+1)}{2}$, let $d = C_s - C$ and let $n = qs + r$ with $0 \le r < s$. We have

$$T(C, n) \le sn - C_s - dq + (5 - 2\sqrt{6})C + \min\{d, s - r\}$$

**Remark** The bounds given on the number of anomalies are close to the exact values. As example for $C = 10$ and $n = 11$ (resp. $C = 21$ and $n = 16$), Theorem 18 gives $An(10, 11) \le 1$ (resp. $An(21, 16) \le 2$) and the bound is attained.

Another example is given with $s = 24$; $C = s(s+1)/2 = 300$ and $n = 60$ ($q = 2, r = 12$). We get by Theorem 17 $[UB(300, 2)] = [30.294] = 30$. The exact value obtained with Theorem 12 shows that for $s = 24$ and $r = 12$ we have $An(300, 36) = 30$. In that case the upper bound is attained.

In Table 2, we give for $C = 192$, and so for $s = 20$ and $d = 18$, some values of $n$ for which the bound on the number of anomalies $M^*(192, q)$ is attained, as can also be observed in Figure 1. We also give the corresponding values of $UB(192, q)$, which shows that $UB(192, q)$ is a good approximation.

<table><caption>Table 2: Values of $n$ for which the upper bound $M^*(192, q)$ on the number of anomalies is attained when $C = 192$.</caption><thead><tr><th>n</th><th>q</th><th>An(192, n) = M*(192, q)</th><th>UB(192, q)</th></tr></thead><tbody><tr><td>48</td><td>2</td><td>18</td><td>19</td></tr><tr><td>68</td><td>3</td><td>12</td><td>13</td></tr><tr><td>88</td><td>4</td><td>9</td><td>10</td></tr><tr><td>107</td><td>5</td><td>7</td><td>8</td></tr><tr><td>127</td><td>6</td><td>6</td><td>7</td></tr><tr><td>147</td><td>7</td><td>5</td><td>6</td></tr><tr><td>166</td><td>8</td><td>4</td><td>5</td></tr><tr><td>167</td><td>8</td><td>4</td><td>5</td></tr><tr><td>186</td><td>9</td><td>4</td><td>5</td></tr><tr><td>205</td><td>10</td><td>3</td><td>4</td></tr><tr><td>206</td><td>10</td><td>3</td><td>4</td></tr></tbody></table>

# 7 Conclusion

In this article, we have completely solved the problem of determining the maximum number of requests which can be groomed in a path with a capacity $C$ on each arc. In particular, we have provided a closed formula to compute this number in constant time. We have shown furthermore that an optimal solution was obtained with a greedy algorithm. We also gave an upper-bound which happens to be useful to compute the cutwidth of a graph. It will be interesting to consider the same problem for other networks in particular to determine networks for which the solution is obtained using independent sets or for which there exists a polynomial algorithm to solve
the problem. Note that for unidirectional rings this problem is easy as the solution is given by considering all the requests of smallest length.

## References

[1] U. Adamy, C. Ambühl, R. S. Anand, and T. Erlebach. Call control in rings. Algorithmica, 47(3):217-238, 2007.

[2] J.-C. Bermond, L. Braud, and D. Coudert. Traffic Grooming on the Path. Theoretical Computer Science, 384(2-3):139-151, 2007.

[3] J.-C. Bermond, M. Cosnard, D. Coudert, and F. Havet. Groupage sur le chemin pour borner la largeur de coupe. In AlgoTel 2023 - 25èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, page 4, Cargèse, France, May 2023.

[4] J.-C. Bermond, M. Cosnard, D. Coudert, and S. Pérennes. Optimal Solution of the Maximum All Request Path Grooming Problem. In Advanced International Conference on Telecommunications (AICT), Le Gosier, Guadeloupe, France, Feb. 2006. IEEE.

[5] M. C. Calisle and E. L. Lloyd. On the *k*-coloring of intervals. Discrete Applied Mathematics, 59(3):225-235, 1995.

[6] J. Díaz, J. Petit, and M. Serna. A survey on graph layout problems. ACM Computing Surveys, 34(3):313-356, 2002.

[7] R. Dutta, S. Huang, and G. N. Rouskas. On optimal traffic grooming in elemental network topologies. In Opticomm, pages 13-24, Oct. 2003.

[8] R. Dutta, A. E. Kamal, and G. N. Rouskas. Traffic Grooming for Optical Networks: Foundations, Techniques and Frontiers. Optical Networks. Springer New York, NY, 2008.

[9] R. Dutta and G. N. Rouskas. A survey of virtual topology design algorithms for wavelength routed optical networks. Optical Networks, 1(1):73-89, Jan. 2000.

[10] T. Erlebach and K. Jansen. Maximizing the number of connections in optical tree network. In 9th International Symposium on Algorithms and Computation (ISAAC'98), pages 179-188. LNCS 1533, 1998.

[11] E. Modiano and P. Lin. Traffic grooming in WDM networks. IEEE Communications Magazine, 39(7):124-129, July 2001.

[12] P. Winkler and L. Zhang. Wavelength assignment and generalized interval graph coloring. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 830-831, 2003.

[13] M. Yannakakis and F. Gavril. The maximum *k*-colorable subgraph problem for chordal graphs. Information Processing Letters, 24(2):133-137, 1987.

[14] K. Zhu and B. Mukherjee. A review of traffic grooming in WDM optical networks: Architectures and challenges. Optical Networks Magazine, 4(2):55-64, 2003.