<figure><img src="image_1.png" /></figure>

HAL
open science

# Maximizing the number of requests in oriented trees
with a grooming factor

Jean-Claude Bermond, Michel Cosnard

► To cite this version:

Jean-Claude Bermond, Michel Cosnard. Maximizing the number of requests in oriented trees with a grooming factor. 2025. hal-05008883

HAL Id: hal-05008883

https://inria.hal.science/hal-05008883v1

Preprint submitted on 27 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Maximizing the number of requests in oriented trees with a grooming factor *

Jean-Claude Bermond and Michel Cosnard

Université Côte d'Azur, Inria, CNRS, I3S, Sophia Antipolis, France
jean-claude.bermond@inria.fr, michel.cosnard@inria.fr

March 27, 2025

## Abstract

The Maximum All Request Path Grooming (MARPG) problem consists in finding the maximum number of requests (connections) which can be established in a network, where each arc has a given capacity or bandwidth $C$ (grooming factor). The Maximum Path Coloring problem consists for a given number of colors (wavelengths) $W$ in finding the maximum number of requests that can be established so that two requests sharing an arc have different colors. These problems are part of the more general RWA (Routing and Wavelength Assignment) problem and have been studied for various classes of networks like paths, dipaths, undirected trees and symmetric directed trees. Here we consider the case where the network is an oriented tree (tree in which each edge has a unique orientation) where the two problems are equivalent. We give the value of the maximum number of requests for various families of oriented trees like Fig-Trees. To do that we revisit the problem when the network is a directed path by giving the structure of a maximum set of requests and determining bounds on the maximum load of an arc of the dipath. These bounds can be used for computing the cutwidth of a graph.

**Keywords :** grooming; requests; path; oriented trees; spiders; cutwidth; path coloring.

## 1 Introduction

We consider the following problem: what is the maximum number of connections that can be established in a network where each arc has a given capacity (bandwidth) $C$. In this article we will consider networks which are oriented trees.

**The MARPG problem** A connection request in a general digraph is given by a sender-receiver pair $(i, j)$. Note that, if the original digraph has the property that for any request $(i, j)$ there is a unique dipath from $i$ to $j$, then it is equivalent to consider a request or the associated dipath. That is the case in oriented trees and more generally in the class of UPP-digraphs (UPP

<footnote>*We are very pleased to dedicate this paper to our friend Ralf Klasing for his 60th birthday. We had the opportunity to work with him in 2002-2005 when he was a CNRS researcher in the project Mascotte at Sophia Antipolis. He studied wavelength routing (see [Kla98]) which was also a hot topic in Mascotte. This is the subject of this paper. Ralf has also done a remarkable work on dissemination of the results on communication in various networks ([HKP$^+$05, BKK$^+$09]). The collaboration with him resulted in particular in fruitful articles on gathering in radio networks (see for example [BGK$^+$06, BKM$^+$13])</footnote>
stands for Unique Path Property) in which there is at most one dipath from a vertex to another (see [BC07]). The load $L(e)$ of an arc $e$ is the number of dipaths (requests) using this arc.

The problem is known in the literature as the *Maximum Path Packing Problem* or *Maximum Path Grooming Problem* or *Maximum Request Grooming (MRG) Problem* and can be restated as follows: Given a grooming (bandwidth) factor what is the maximum number of simple requests (any request appears at most once) that can be routed (groomed) together such that the load of any arc is at most *C*. In the general problem the requests have to be taken among a given set of requests (or dipaths). Here we consider all the possible requests and in that case the problem is called *Maximum All request Path Grooming (MARPG) Problem*. A similar problem has been widely considered in the case of optical networks. To each request is assigned a color (wavelength). Then the *Maximum Path Coloring problem* consists for a given number of colors (wavelengths) *W* in finding the maximum number of requests that can be established so that two requests sharing an arc have different colors.

In general the two problems are different but it has been proved that for any set of requests the minimum number of wavelength is equal to the maximum load in directed trees ( [GHP97]) and UPP digraphs ( [BC07]) and so the two problems are equivalent. These two problems are part of the more general RWA (Routing and Wavelength Assignment) problem (see for example [BBG$^{+}$97, Kla98, DR02].

**Previous results for a dipath** When the network is a directed path the MARPG problem is also known as the *Call Control Problem in Path Networks* ( [AAAE07]). It was first motivated by traffic grooming in an optical path network (see [BBC07] and [DHR03]) and then by computation of the cutwidth of a graph (see [BCCH23] for more details). The maximum number of requests $T(C, n)$ in a dipath with $n$ vertices 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) \geq C^*(m, n) = \min\{C \mid m \leq T(C, n)\}$ (see [BCCH23] for more details). This lower bound is also used in [DPS02] (bound $LB_4$) but with false values for $T(C, n)$.

As noted in [EJ98, WZ03] 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 [CL95, YG87]. The best known algorithm is given in [CL95] 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 [BCCP24] (see also Theorem 24 of this article). 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 [DPS02]). In [BCCP24] we showed that the conjecture is false. Then, we determined exactly for any *n* and *C* the optimal value of $T(C, n)$. Finally, we provided some upper bounds on this value, and more precisely on the difference between $T(C, n)$ and the number of requests of the greedy solution.

**Previous results for trees and directed trees** Both the maximum path coloring problem and the MRPG problem have been widely considered for trees and directed trees (here each edge of a tree is replaced by two opposite arcs). In general the problem is NP-hard and approximations algorithms have been given (see for example [DHR03, EJK$^{+}$99, EJ98, EJ01, GHP97, GV00, HDR06]. In particular in [EV06] is it proven that for directed generalized stars (also called directed spiders) the (weighted) MRPG problem can be solved optimally in polynomial time by reducing it to the minimum cost network flow problem. However as far as we know the problem has not been studied for oriented trees (obtained from an undirected by assigning to each edge an
orientation). Furthermore we want to give closed formula for the maximum number of requests (and also give a set of requests attaining this number).

**Our results** In this article we solve the problem for some particular types of oriented trees. The paper is organized as follows. In section 2 we define precisely the types of trees considered (called Fig-Trees) and give the exact value of the maximum number of requests that can be groomed in these trees. As the proof is involved we give a sketch of the proof illustrated for small values of *C* in section 3.

To do the complete proof we need to revisit the problem for dipaths. In section 4 we characterize the set of requests in optimal solutions. That extends the work done in [BCCH23] where we only determine their number. For that we describe precisely the structure of what we call anomalies which are roughly requests which appear in an optimal solution but not in the greedy solution (consisting of the *C* requests of smallest length) (see the exact definitions in section 4). This characterization is interesting in itself and enables us to determine the maximum load of an arc of the dipath in section 5 (this result can be used to cut branches in branch and bounds algorithms computing the cutwidth of a digraph). In section 6 we give the proof of the number maximum number of requests that can be groomed in the special trees considered.

In section 7 we show how to extend the results for other oriented trees (generalized Fig-Trees). Finally in section 9 we attack the problem for oriented Spider-Trees giving a conjecture that we prove in various cases.

## 2 Definitions and results

An (oriented) dipath consists of a set of vertices {$i : 1 \le i \le n$}, plus all the ordered pairs $(i, i+1)$ called arcs.

In this article we consider oriented trees where all the paths are oriented from a root with in-degree 0 and out-degree 1 to a leaf with in-degree 1 and out-degree 0 and in particular Fig-Trees. A Fig-Tree $F = (\mathcal{A}, (a, b), \mathcal{B})$ consists of a set $\mathcal{A}$ of dipaths ending in a vertex $a$, plus an arc $(a, b)$ called trunk and a set $\mathcal{B}$ of dipaths starting in the vertex $b$ (see Figure 1). The simplest Fig-Trees (not a dipath) are the $Y$-tree and the $\perp$-tree where there are all together 3 dipaths with at least one in $\mathcal{A}$ and one in $\mathcal{B}$. The $Y$-tree $(A, (a, b), B \cup B')$ consists of a dipath $A$ ending in $a$, a trunk $(a, b)$ and two dipaths $B, B'$ starting in $b$. The $\perp$-tree $(A \cup A', (a, b), B)$ consists of two dipaths $A, A'$ ending in $a$, a trunk $(a, b)$ and a dipath starting in $B$. These trees are also known as the spiders $(A \cup (a, b), b, B \cup B')$ and $S = (A \cup A', a, (a, b) \cup B)$ (see section 8). We note that a $\perp$-tree is obtained from an $Y$-tree by reversing all the arcs.

If there exists in the oriented tree a dipath from a vertex $i$ to a vertex $j$, we define the request $(i, j)$ both as a couple of vertices and as the dipath from vertex $i$ to vertex $j$. We do not allow multiple requests. By definition, the request $(i, j)$ loads with load 1 all the arcs of the dipath 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$.

We will denote by $T(C, P)$ the maximum number of requests that can be groomed on a dipath $P$ with a grooming factor $C$. We denote by $T(C, \mathcal{A})$ the maximum number of requests that can be groomed in the dipaths of $\mathcal{A}$ with a grooming factor $C$: $T(C, \mathcal{A}) = \sum T(C, A^i)$, where the $A^i$ are the dipaths of $\mathcal{A}$. Similarly we denote by $T(C, \mathcal{B})$ the maximum number of requests that can be groomed in the dipaths of $\mathcal{B}$ with a grooming factor $C$: $T(C, \mathcal{B}) = \sum T(C, B^j)$, where the $B^j$ are the dipaths of $\mathcal{B}$.
<figure><img src="image_3.png" /><figcaption>(1) Fig Tree= $(\mathcal{A}, (a, b), \mathcal{B})$</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(2) $Y = (A, (a, b), B \cup B')$</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(3) $\perp = (A \cup A', (a, b), B)$</figcaption></figure>

<caption>Figure 1: Examples of Fig Trees where $A^i$ and $B^i$ are dipaths.</caption>
**Proposition 1** Let $T(C, F)$ be the maximum number of requests that can be groomed in a Fig-Tree $F = (\mathcal{A}, (a, b), \mathcal{B})$. Then:

$$T(C, F) \leq C + T(C, \mathcal{A}) + T(C, \mathcal{B})$$

**Proof.** The requests inside $\mathcal{A}$ and $\mathcal{B}$ are disjoint and in number at most $T(C, \mathcal{A}) + T(C, \mathcal{B})$. Those between a vertex in $\mathcal{A}$ and a vertex in $\mathcal{B}$ use the arc $(a, b)$ and so their number is at most $C$. Therefore, $T(C, F) \leq C + T(C, \mathcal{A}) + T(C, \mathcal{B})$. $\square$

The next theorem (Theorem 2) gives the exact value of the maximum number of requests that can be groomed in a general Fig-Tree.

**Theorem 2** Let $C \geq 3$ and let $F = (\mathcal{A}, (a, b), \mathcal{B})$ be a Fig-Tree where $\mathcal{A}$ and $\mathcal{B}$ are not empty and three of the dipaths of $\mathcal{A} \cup \mathcal{B}$ have a number of vertices $\geq s$. Then the maximum number of requests $T(C, F)$ that can be groomed in $F$ is:

$$T(C, F) = C + T(C, \mathcal{A}) + T(C, \mathcal{B})$$

We will show that to prove Theorem 2 is sufficient to prove it for the simplest case of a Y-tree. So, we emphasize the Theorem 2 for the Y-tree as Theorem 3.

**Theorem 3** Let $C \geq 3$ and let $Y = (A, (a, b), B \cup B')$ be an Y-Tree where the dipaths of $A, B, B'$ have a number of vertices $\geq s$. Then the maximum number of requests $T(C, Y)$ that can be groomed in $Y$ is:

$$T(C, Y) = C + T(C, A) + T(C, B) + T(C, B')$$

**Proof that Theorem 2 follows from Theorem 3**

We first note that Theorem 3 implies the value of Theorem 2 for the $\perp$-trees. Indeed let $\perp = (A \cup A', (a, b), B)$ be a $\perp$-tree. If we reverse the arcs of this $\perp$-tree we get the Y-tree $Y = (B, (b, a), A \cup A')$. For each request $(i, j)$ of the Y-tree we associate the request $(j, i)$ in the associated $\perp$-tree. Doing so we build a set of $C + T(C, B) + T(C, A) + T(C, A')$ in the $\perp$-tree which is maximum by Proposition 1, so proving Theorem 2 for $\perp$-trees.

Now we are able to prove Theorem 2. Let the three dipaths of the hypothesis be $P^1, P^2, P^3$ with $P^1$ in $\mathcal{A}, P^3$ in $\mathcal{B}$. Consider the tree formed by the three paths $P^1, P^2, P^3$ plus the trunk $(a, b)$. It is an Y-tree (resp a $\perp$-tree) if $P^2$ belongs to $\mathcal{A}$ (resp. $\mathcal{B}$). In both cases we can groom on it $C + T(C, P^1) + T(C, P^2) + T(C, P^3)$ requests. Then we add the maximum number of requests on the other dipaths of $\{\mathcal{A} \cup \mathcal{B}\}$ minus $\{P^1 \cup P^2 \cup P^3\}$ and so we can groom $C + T(C, \mathcal{A}) + T(C, \mathcal{B})$ requests which is a maximum set by Proposition 1.

## 3 Sketch of proof of Theorem 3

The proof is involved and will be the object of section 6. We just give here the main ideas. Let $Y = (A, (a, b), B \cup B')$ be an Y-Tree, where $A = (a_{n_A}, a_{n_A-1}, \dots, a_2, a_1 = a)$ and $B = (b = b_1, b_2, \dots, b_{n_B-1})$ and $B' = (b = b'_1, b'_2, \dots, b'_{n_{B'}-1})$ with $n_A, n_B, n_{B'} \geq s$. We first put the maximum number of requests on $A, B, B'$. Then we will add $C$ requests joining vertices of $A$ to vertices of $B$ and $B'$ (therefore containing the trunk $(a, b)$), in such a way that the load of the arcs of $A, B, B'$ does not exceed $C$.

The proof needs first a careful computation of the maximum load $P_i$ (abbreviation of $P_i(C)$) of the arc $(i, i+1)$, $1 \leq i \leq s$ of a dipath done in Section 5 (using the characterization of the set of maximum requests done in Section 4). It will appear that the arcs at the end of the dipath have load smaller than $C$ and so there is room to add $C$ requests between $A$ and $B, B'$.
Let $R_i$ (abbreviation of $R_i(C)$) denote the number of new requests starting in $a_i$. We have $\sum_{k \ge 1} R_k = C$. The load on the arc $(a_{i+1}, a_i)$ due to the new requests is $N_i = C - \sum_{k=1}^{k=i} R_k$ and so the total load on the arc $(a_{i+1}, a_i)$ is $L_i^A = P_i + C - \sum_{k=1}^{k=i} R_k$. In order that $L_i^A \le C$, the $R_i$ should satisfy

$$ \text{For all } i \quad \sum_{k=1}^{k=i} R_k \ge P_i \quad (*) $$

Let $x$ be the smallest integer such that $\sum_{k=1}^{k=x} R_k \ge C$. So there are no requests starting from a node $a_i$ with $i > x$. In the example below and for the values of $C \le 15$ we will choose the $R_i$ $1 \le i \le x-1$ such that $\sum_{k=1}^{k=i} R_k = P_i$. In that case $R_1 = P_1$; for $2 \le i \le x-1$, $R_i = P_i - P_{i-1}$ and $R_x = C - \sum_{k=1}^{x-1} R_k$. Doing so the load on the arcs of $A$ does not exceed $C$. The load on the arc $(a_1 = a, b = b_1 = b'_1)$ is exactly $C$. Then it remains to show that the load on the arcs of $B$ and $B'$ does not exceed $C$.

Let us show how it works on an example. Let $C = 10$ and $n = 11$ (the smallest values for which the greedy solution is not optimal). The greedy solution consists of all the requests of size $\le 4$. The optimal solution is obtained by replacing the request (4, 8) of size 4 by the two requests (1, 6), (6, 11). In the optimal solution the load $P_1$ on the arc (1, 2) is 5 (it was 4 in the greedy solution). We have $P_2 = 7+1=8$ and then for $3 \le i \le 8$, $P_i = 10$. So we choose $R_1 = P_1 = 5$; $R_2 = P_2 - P_1 = 3$; $R_3 = C - P_2 = 2$.

The 5 requests issued from $a_1 = a$ will be $(a_1 = a, b = b_1 = b'_1 - 1)$ and then $(a_1, b_2)$, $(a_1, b'_2)$, $(a_1, b_3)$, $(a_1, b'_3)$. The 3 requests issued from $a_2$ will be $(a_2, b)$ and then $(a_2, b_2)$, $(a_2, b'_2)$. The 2 requests issued from $a_3$ will be $(a_3, b)$ and then $(a_3, b_2)$. There is no requests starting from an $a_i$ with $i \ge 4$. The load on the arc $(a, b)$ is 10. The load on the arc $(a_2, a_1)$ due to the new requests is 5 and the total load is $P_1 + 5 = 10$. The load on the arc $(a_3, a_2)$ due to the new requests is 2 and the total load is $P_2 + 2 = 10$. The load on the arc $(b_1, b_2)$ (resp. $(b'_1, b'_2)$) due to the new requests is $2+1+1=4$ (resp $2+1$) and the total load is at most $P_1 + 4 = 9$. The load on the arc $(b_2, b_3)$ (resp. $(b'_2, b'_3)$) due to the new requests is 1 and the total load is $P_2 + 1 = 9$. Therefore we have the desired solution.

In the next table we indicate for $6 \le C \le 15$ the values of the load $P_i$ of the arc $(i, i+1)$ within the optimal solution. The first value corresponds to the load of the greedy solution and the +1 corresponds to an extra load in the optimal solution for some values of $n$ (the worst case). We note that, for $i \ge 4$, $P_i = C$ and so we give the values only for $i \le 3$. Then we indicate the values of $R_i = P_i - P_{i-1}$ and those of the load on the arc $(a_{i+1}, a_i)$ due to the new requests $N_i^A$. The values are chosen in such a way that the load of $(a_{i+1}, a_i)$ and $(a, b)$ is at most $C$. The $R_i$ new requests are chosen to join $a_i$ to $b_1$ and the $b_j$ with $2 \le j \le [(R_i + 1)/2]$ and the $b'_j$ with $2 \le j \le [(R_i + 1)/2]$. With this choice, the load of $(b_j, b_{j+1})$ is always greater than or equal to that of $(b'_j, b'_{j+1})$. Then we give the values of the load $N_j^B$ on the arc $(b_j, b_{j+1})$ due to these new requests and the total load $L_j^B = P_j + N_j^B$. For $i \ge 3$ $N_j^B = 0$ and so $L_j^B \le C$ except for $C = 14$ and $C = 15$ where $N_j^B = 1$, but then in that case $L_j^B = 14 < C$.

# 4 Characterization of the set of anomalies

In [BCCP24] we compute the maximal number of requests $T(C, n)$ that can be groomed on a path with $n$ vertices with a grooming factor by designing a specific optimal solution. In order to be complete we recall now briefly some definitions and results of [BCCP24] which will be useful to compute the load on the arc $(i, i+1)$ of this optimal solution.
<table><caption>Table 1: Values of $P_i$, $R_i$, $N_i^B$ and $L_i^B$ for small $C$</caption><thead><tr><th>s</th><th>C</th><th>P<sub>1</sub></th><th>P<sub>2</sub></th><th>P<sub>3</sub></th><th>R<sub>1</sub></th><th>R<sub>2</sub></th><th>R<sub>3</sub></th><th>R<sub>4</sub></th><th>N<sub>1</sub><sup>A</sup></th><th>N<sub>2</sub><sup>A</sup></th><th>N<sub>3</sub><sup>A</sup></th><th>N<sub>1</sub><sup>B</sup></th><th>L<sub>1</sub><sup>B</sup></th><th>N<sub>2</sub><sup>B</sup></th><th>L<sub>2</sub><sup>B</sup></th></tr></thead><tbody><tr><td>3</td><td>6</td><td>3</td><td>5</td><td>6</td><td>3</td><td>2</td><td>1</td><td>0</td><td>3</td><td>1</td><td>0</td><td>2</td><td>5</td><td>0</td><td>5</td></tr><tr><td>4</td><td>7</td><td>4</td><td>6</td><td>7</td><td>4</td><td>2</td><td>1</td><td>0</td><td>3</td><td>1</td><td>0</td><td>3</td><td>7</td><td>1</td><td>7</td></tr><tr><td>4</td><td>8</td><td>4</td><td>7</td><td>8</td><td>4</td><td>3</td><td>1</td><td>0</td><td>4</td><td>1</td><td>0</td><td>3</td><td>7</td><td>1</td><td>8</td></tr><tr><td>4</td><td>9</td><td>4</td><td>7</td><td>9</td><td>4</td><td>3</td><td>2</td><td>0</td><td>5</td><td>2</td><td>0</td><td>4</td><td>8</td><td>1</td><td>8</td></tr><tr><td>4</td><td>10</td><td>4+1</td><td>7+1</td><td>9+1</td><td>5</td><td>3</td><td>2</td><td>0</td><td>5</td><td>2</td><td>0</td><td>4</td><td>9</td><td>1</td><td>9</td></tr><tr><td>5</td><td>11</td><td>5</td><td>8</td><td>10</td><td>5</td><td>3</td><td>2</td><td>1</td><td>6</td><td>3</td><td>1</td><td>4</td><td>9</td><td>1</td><td>9</td></tr><tr><td>5</td><td>12</td><td>5</td><td>9</td><td>11</td><td>5</td><td>4</td><td>2</td><td>1</td><td>7</td><td>3</td><td>1</td><td>5</td><td>10</td><td>2</td><td>11</td></tr><tr><td>5</td><td>13</td><td>5</td><td>9</td><td>12</td><td>5</td><td>4</td><td>3</td><td>1</td><td>8</td><td>4</td><td>1</td><td>5</td><td>10</td><td>2</td><td>11</td></tr><tr><td>5</td><td>14</td><td>5+1</td><td>9+1</td><td>12+1</td><td>6</td><td>4</td><td>3</td><td>1</td><td>8</td><td>4</td><td>1</td><td>6</td><td>12</td><td>3</td><td>13</td></tr><tr><td>5</td><td>15</td><td>5+1</td><td>9+1</td><td>12+1</td><td>6</td><td>4</td><td>3</td><td>2</td><td>9</td><td>5</td><td>2</td><td>7</td><td>13</td><td>3</td><td>13</td></tr></tbody></table>

$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$. We do not allow multiple requests. 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.

In what follows we denote by $C$ the grooming factor and we let $s$ be the integer such that $C_{s-1} < C \le C_s$, where $C_s = \frac{s(s+1)}{2}$ and we let $d = C_s - C$. The grooming factor $C$ being given, the Maximum All Request Path Grooming problem (MARPG) 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)$.

There are many ways of structuring the requests with the same size. We choose to consider maximal sets of independent requests where two requests are said to be independent if the associated sub-paths have no arc in common.

**Definition 4** 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$. The number of requests of the independent set $I(\sigma, t)$ is $w(\sigma, t) = \lfloor \frac{n-t}{\sigma} \rfloor$, and will be called the weight of $I(\sigma, t)$.

For example, $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+3)$ (resp. $(2j+2, 2j+4)$) and so on we have $I(\sigma, t) = \{(t, t+\sigma), (t+\sigma, t+2\sigma), \dots\}$. For $n=11$, the independent sets are the following: $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 so the load due to the requests of an independent set is at most one on each arc. Therefore any solution consisting of $C$ independent sets is feasible
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 but it is not necessarily the
case. More precisely we introduce the following order on the independent sets

**Definition 5** (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'$.

With this definition we get the following characterization.

**Property 6** The greedy solution is obtained by taking the $C$ first independent sets in the increasing lexicographic order of the independent sets. More precisely if $C = s(s+1)/2 - d$ then the greedy solution is composed of all the independent sets of size $\sigma \le s - 1$ plus the first $s - d$ independent sets of size $s$ in the lexicographic order.

As seen in the introduction the greedy solution is not necessarily optimum. In [BCCP24] we
characterize the optimal solutions

**Theorem 7** [*BCCP24*] Any solution obtained by taking the $C$ independent sets with the largest weights is optimal and contains the maximum number of requests $T(C, n)$.

**Definition 8** (*Weight order*). A weight order will denote any order in which if an independent set $I(\sigma, t)$ has a larger weight than another independent set $I(\sigma', t')$, that is if $w(I(\sigma, t)) > w(I(\sigma', t'))$, then $I(\sigma, t)$ appears before $I(\sigma', t')$.

We can rephrase Theorem 7 as follows: Any solution obtained by taking the $C$ first indepen-
dent sets in an increasing weight order of the independent sets is optimal.

Note that there might exist many weight orders and so many optimum solutions (with $T(C, n)$ requests) as we did not precise the order of the independent sets with equal weight. Indeed let $w(C)$ be the largest integer such that there are at least $C$ independent sets with weight $w \ge w(C)$. So an optimal solution consists of the $C^+$ independent sets with weight strictly larger than $w(C)$ plus $C - C^+$ independent sets of weight $w(C)$. However there might exist $C' > C - C^+$ independent sets of weight equal to $w(C)$ and so different choices of $C - C^+$ sets among these $C'$ sets give rise to different optimal solutions.

In what follows (to ease the computing) we will consider only greedy compatible weight orders
and the associated optimum solutions $S^*$ called greedy compatible optimal solutions defined as
follows.

**Definition 9** (*greedy compatible weight orders and greedy compatible optimal solutions*)

In a greedy compatible weight order, let $I(\sigma, t)$ and $I(\sigma', t')$ have the same weight ($w(I(\sigma, t)) = w(I(\sigma', t'))$). If both $I(\sigma, t)$ and $I(\sigma', t')$ belong to the greedy solution, then they are ordered lexicographically. If $I(\sigma, t)$ belongs to the greedy solution, and $I(\sigma', t')$ does not then $I(\sigma, t)$ is ordered before $I(\sigma', t')$. If none belongs to the greedy solution they are ordered in any order. **A greedy compatible optimal solution** $S^*$ is obtained by taking the $C$ first independent sets in an increasing greedy compatible weight order of the independent sets.

**Property 10** Let $S_1^*$ and $S_2^*$ be greedy compatible optimal solutions. If $I(\sigma, t)$ belongs to the greedy solution and to $S_1^*$, then $I(\sigma, t)$ belongs to $S_2^*$.

**Definition 11** An anomaly (for a greedy compatible optimal solution $S^*$) is an independent set which appears in the greedy compatible optimal solution $S^*$, but does not appear in the greedy solution.
The advantage of considering only greedy compatible weight orders is that, by Property 10, the number of anomalies is the same for any greedy compatible optimal solution. We emphasize this fact in the following proposition.

**Proposition 12** The number of anomalies is the same for any greedy compatible optimal solution and their number 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^*$).

For example when $n = 11$ and $C = 10$ then the greedy solution consists of all requests of size $\le 4$, that is all the independent sets $I(\sigma, t)$ with $1 \le t \le \sigma \le 4$ while the optimal solution consists of all the independent sets of weight $\ge 2$ and is obtained by removing the independent set $I(4, 4) = \{(4, 8)\}$ of weight 1 and adding the independent set $I(5, 1) = \{(1, 6), (6, 11)\}$ of weight 2 which is an anomaly. This solution is unique as there are exactly 10 sets of weight $\ge 2$.

Another simple example is given for $s = 6$, $C = 21$ and $n = 16$. The greedy solution consists of the 21 first independent sets $I(\sigma, t)$ in the lexicographic order (with $1 \le t \le \sigma \le 6$) while the optimal solution consists of all the independent sets of weight $\ge 2$ and is obtained by removing from the greedy solution two independent sets $I(6, 5)$ and $I(6, 6)$, each of weight 1, and adding the two independent sets $I(7, 1)$ and $I(7, 2)$ each of weight 2 which are anomalies. This solution is unique as there are exactly 21 sets of weight $\ge 2$.

Let $s$ be the integer such that $C_{s-1} < C \le C_s$, where $C_s = \frac{s(s+1)}{2}$ and $d = C_s - C$.

In [BCCP24] we prove that if $n \le 2s$ there are no anomalies as the greedy solution is optimal. So in what follows we suppose that $n = qs + r$, where $q \ge 2$ and $0 \le r \le s - 1$ and $S^*$ will be a greedy compatible optimal solution.

We first note the three 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$.

- Property C: the independent sets of $R$ with $\sigma = s$ have weight $q$ if $t \le r$ and weight $q - 1$ if $t > r$. Indeed $t + qs = n + t - r$.

By Property B, the independent sets with weight $\ge q + 1$ satisfy $\sigma \le s - 1$. 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 greedy compatible optimal solution $S^*$. By Property A, the sets with weight $\le q - 2$ satisfy $\sigma \ge s + 1$ and so they are ranked after rank $s(s+1)/2 \ge C$. So, they do not appear neither in the greedy solution nor in the greedy compatible optimal solution $S^*$.

Therefore any greedy compatible optimal solution $S^*$ is obtained from the greedy solution by replacing some independent sets of size $q - 1$ with some independent sets of size $q$ (the anomalies). So, we have to know what are the independent sets of weight $q$ not in the greedy solution and the independent sets of weight $q - 1$ in the greedy solution.

**Definition 13** Let $\mathcal{A}(s, r, q)$ (resp. $\mathcal{A}^s(s, r, q)$) denote the set of independent sets of weight $q$ and of size $\ge s + 1$ (resp. of size $s$) which are not in the greedy solution and let $\mathcal{A}(s, r, q)$ (resp. $\mathcal{A}^s(s, r, q)$) denote its cardinality. We call $\mathcal{A}'(s, r, q)$ the union of $\mathcal{A}(s, r, q)$ and $\mathcal{A}^s(s, r, q)$ and we let $\mathcal{A}'(s, r, q)$ denote its cardinality.
**Definition 14** Similarly, let $\mathcal{G}(s,r,q)$ (resp. $\mathcal{G}^s(s,r,q)$) denote the set of independent sets of weight $q-1$ and of size $\le s-1$ (resp. of size $s$) in the greedy solution and let $\mathcal{G}(s,r,q)$ (resp. $\mathcal{G}^s(s,r,q)$) denote its cardinality. We call $\mathcal{G}'(s,r,q)$ the union of $\mathcal{G}(s,r,q)$ and $\mathcal{G}^s(s,r,q)$ and we let $\mathcal{G}'(s,r,q)$ denote its cardinality.

We will now characterize the set of anomalies and its cardinality via various claims

**Claim 15** If $A'(s,r,q) \le G'(s,r,q)$, then the anomalies are exactly the independent sets of $A'(s,r,q)$ while if $G'(s,r,q) < A'(s,r,q)$ the anomalies consist of the first $G'(s,r,q)$ independent sets of $A'(s,r,q)$.

Note that in the first case the set of anomalies is the same for any solution $S^*$ while in the second case it might depend of the greedy compatible optimal solution $S^*$ chosen (the number of anomalies being the same for all the greedy compatible optimal solutions $S^*$).

We illustrate the definitions via an example which can help the reader to follow the claims.

**Example for $s = 10, C = 55-d$ with $0 \le d \le 9$ and $q = 2$**

* If $r \le 2$ ($n = 21, 22$), $\mathcal{A}(10, r, 2) = \emptyset$

* If $r = 3$ ($n = 23$), $\mathcal{A}(10, 3, 2) = I(11, 1) = \{(1, 12), (12, 23)\}$

* If $r = 4$ ($n = 24$), $\mathcal{A}(10, 4, 2)$ contains furthermore $I(11, 2) = \{2, 13\}, (13, 24)\}$

* If $r = 5$ ($n = 25$), $\mathcal{A}(10, 5, 2)$ contains furthermore $I(11, 3) = \{3, 14\}, (14, 25)\}$ and $I(12, 1) = \{1, 13\}, (13, 25)\}$

* If $r = 6$ ($n = 26$), $\mathcal{A}(10, 6, 2)$ contains furthermore $I(11, 4) = \{4, 15\}, (15, 26)\}$ and $I(12, 2) = \{2, 14\}, (14, 26)\}$

* If $7 \le r \le 9$ ($n = 27, 28, 29$), $\mathcal{G}(10, r, 2) = \emptyset$

* If $r = 6$ ($n = 26$), $\mathcal{G}(10, 6, 2)$ contains $I(9, 9) = (9, 18)$

* If $r = 5$ ($n = 25$), $\mathcal{G}(10, 5, 2)$ contains furthermore $I(9, 8) = (8, 17)$

* If $r = 4$ ($n = 24$), $\mathcal{G}(10, 4, 2)$ contains furthermore $I(9, 7) = (7, 16)$

* If $r = 3$ ($n = 23$), $\mathcal{G}(10, 3, 2)$ contains furthermore $I(9, 6) = (6, 15)$ and $I(8, 8) = (8, 16)$

* If $r \le 10-d$, $\mathcal{A}^s(10, r, 2)$ is empty while $\mathcal{G}^s(10, r, 2)$ contains the $10-d-r$ independent sets $I(10, t)$ with $r+1 \le t \le 10-d$.

* If $r > 10-d$, then $\mathcal{G}^s(10, r, 2)$ is empty while $\mathcal{A}^s(10, r, 2)$ contains the $r+d-10$ sets $I(10, t)$ with $10-d+1 \le t \le r$.

Let $C = 55$ ($d = 0$).

For $r = 5$, $\mathcal{A}'(10, 5, 2) = \mathcal{A}(10, 5, 2)$ and so $\mathcal{A}'(10, 5, 2) = 4$. $\mathcal{G}(10, 5, 2) = 2$; $\mathcal{G}^s(10, 5, 2) = 5$ and so $\mathcal{G}'(10, 5, 2) = 7$. Therefore the set of anomalies is $\mathcal{A}(10, 5, 2) = I(11, 1) \cup I(11, 2) \cup I(11, 3) \cup I(12, 1)$.

For $r = 6$, $\mathcal{A}'(10, 6, 2) = \mathcal{A}(10, 6, 2)$ and so $\mathcal{A}'(10, 6, 2) = 6$. $\mathcal{G}(10, 6, 2) = 1$; $\mathcal{G}^s(10, 6, 2) = 4$ and so $\mathcal{G}'(10, 5, 2) = 5$. Therefore, the set of anomalies consists of any 5 sets of $\mathcal{A}'(10, 6, 2) = \mathcal{A}(10, 6, 2)$ for example $I(11, 1) \cup I(11, 2) \cup I(11, 3) \cup I(11, 4) \cup I(12, 1)$. It is a maximum set of anomalies for $C = 55$. Indeed, for $r \le 4$, $\mathcal{A}'(10, r, 2) \le 2$ and for $r \ge 7$, $\mathcal{G}'(10, r, 2) \le 3$.
Let $C = 47$ ($d = 8$).

For $r = 3$, $\mathcal{A}'(10, 3, 2) = \mathcal{A}(10, 3, 2) \cup \mathcal{A}^s(10, 3, 2) = I(11, 1) \cup I(10, 3)$ and so $A'(10, 3, 2) = 2$ while $\mathcal{G}'(10, 3, 2) = \mathcal{G}(10, 3, 2)$ and so $G'(10, 3, 2) = 5$. Therefore the set of anomalies is $I(10, 3) \cup I(11, 1)$.

For $r = 4$, $\mathcal{A}'(10, 4, 2) = \mathcal{A}(10, 4, 2) \cup \mathcal{A}^s(10, 4, 2) = I(11, 1) \cup I(11, 2) \cup I(10, 3) \cup I(10, 4)$ and so $A'(10, 4, 2) = 4$, while $\mathcal{G}'(10, 4, 2) = \mathcal{G}(10, 4, 2)$ and so $G'(10, 4, 2) = 3$. Therefore, the set of anomalies consists of any 3 sets of $\mathcal{A}'(10, 4, 2)$ for example $I(10, 3) \cup I(10, 4) \cup I(11, 1)$. It is a maximum set of anomalies for $C = 47$. Indeed, for $r \le 2$, $A'(10, r, 2) = 0$ and for $r \ge 5$, $G'(10, r, 2) \le 2$.

**Claim 16** Let $r = aq + \alpha$, where $0 \le \alpha \le q - 1$. Then

$$ \mathcal{A}(s, r, q) = \bigcup_{k=1}^{a} \bigcup_{t=1}^{r-kq} I(s+k, t) \\ A(s, r, q) = ar - \frac{a(a+1)}{2}q = \frac{r^2 - qr + \alpha(q - \alpha)}{2q} $$

*Proof.* For $1 \le k \le a$, there are $r - kq$ independent sets of weight $q$ in $R(s+k)$ namely the sets $I(s+k, t)$ where $1 \le t \le r-kq$. So, summing on $k$ we get $A(s, r, q) = \sum_{k=1}^{k=a} (r-kq) = ar - \frac{a(a+1)}{2}q$. Using $a = (r - \alpha)/q$, we get the formula of the claim. $\diamond$

**Claim 17** Let $s - r = b(q + 1) + \beta$, where $0 \le \beta \le q$. Then

$$ \mathcal{G}(s, r, q) = \bigcup_{h=1}^{b} \bigcup_{t=r+qh+1}^{s-h} I(s-h, t) \\ G(s, r, q) = b(s-r) - \frac{b(b+1)}{2}(q+1) = \frac{(s-r)^2 - (q+1)(s-r) + \beta(q+1-\beta)}{2(q+1)} $$

*Proof.* For $1 \le h \le b$, there are $s - r - h(q + 1)$ independent sets of weight $q - 1$ in $R(s - h)$ namely the sets $I(s - h, t)$ with $r + qh + 1 \le t \le s - h$. So, summing on $h$ we get $G(s, r, q) = \sum_{h=1}^{h=b} (s - r - h(q + 1)) = b(s - r) - \frac{b(b+1)}{2}(q + 1)$. Using $b(q + 1) = s - r - \beta$ we get the formula of the claim. $\diamond$

**Claim 18**

$$ \begin{array}{l} \text{If } r \le s - d, \mathcal{A}^s(s, r, q) = \emptyset \text{ and } \mathcal{G}^s(s, r, q) = \bigcup_{t=r+1}^{s-d} I(s, t) \\ \\ \text{If } r \ge s - d, \mathcal{A}^s(s, r, q) = \bigcup_{t=s-d+1}^{r} I(s, t) \text{ and } \mathcal{G}^s(s, r, q) = \emptyset \\ \\ \mathcal{A}^s(s, r, q) = \max\{0, r + d - s\} \quad \text{and} \quad \mathcal{G}^s(s, r, q) = \max\{0, s - r - d\} \end{array} $$

*Proof.* By property (C), the first $r$ independent sets $I(s, t)$ of $R$ with $t \le r$ have weight $q$ while the last $s - r$ ones have weight $q - 1$. By definition of $d$, the first $s - d$ independent sets are in the greedy solution while the last $d$ ones are not in the greedy solution. Two cases can happen:
If $r \le s - d$, then the greedy solution contains $s - d - r$ independent sets of size $s$ with weight $q - 1$ and there are no sets of size $s$ and weight $q$ outside the greedy solution. In that case $\mathcal{A}^s(s, r, q)$ is empty while $\mathcal{G}^s(s, r, q)$ contains the $s - r - d$ independent sets $I(s, t)$ with $r + 1 \le t \le s - d$ and so $\mathcal{G}^s(s, r, q) = s - r - d$.

If $r \ge s - d$, then all the independent sets of size $s$ of the greedy solution have weight $q$ while $r+d-s$ independent sets not in the greedy solution have weight $q$. In that case $\mathcal{G}^s(s, r, q)$ is empty while $\mathcal{A}^s(s, r, q)$ contains the $r+d-s$ sets $I(s, t)$ with $s-d+1 \le t \le r$ and so $\mathcal{A}^s(s, r, q) = s - r - d$.

We can summarize the two cases with the last part of the claim ◇

**Claim 19** If $q > 2$ $\mathcal{A}'(s, r, q) \subset \mathcal{A}'(s, r, 2)$ and $\mathcal{G}'(s, r, q) \subset \mathcal{G}(s, r, 2)$.

*Proof.* We note that if $q > 2$ for a given $r$ the set $\mathcal{A}(s, r, q)$ is strictly included in the set $\mathcal{A}(s, r, 2)$. Similarly the set $\mathcal{G}(s, r, q)$ is strictly included in the set $\mathcal{G}(s, r, 2)$. Furthermore both $\mathcal{A}^s(s, r, q)$ and $\mathcal{G}^s(s, r, q)$ are independent of $q$. So, $\mathcal{A}'(s, r, q)$ is strictly included in the set $\mathcal{A}'(s, r, 2)$ and $\mathcal{G}'(s, r, q)$ is strictly included in the set $\mathcal{G}(s, r, 2)$. ◇

According to the preceding claim, to determine the maximum number of anomalies (and so the maximum number of requests that can be groomed with a grooming factor $C$ on a path of $n$ vertices) and also **to determine the maximum load induced on the arc $(i, i+1)$ it suffices to study the case $q=2$ that is $n=2s+r$ with $0 \le r \le s-1$**.

**Claim 20**

$$A'(s, r, 2) = A(s, r, 2) + \max\{0, r + d - s\} = \frac{r^2 - 2r + \alpha}{4} + \max\{0, r + d - s\}$$

$$G'(s, r, 2) = B(s, r, 2) - d + \max\{0, r + d - s\} = \frac{(s-r)^2 + 3(s-r) + \beta(3-\beta)}{6} - d + \max\{0, r + d - s\}$$

*Proof.* Using for $q = 2$ the values computed for $\mathcal{A}^s(s, r, q)$ in Claim 18 and for $\mathcal{A}(s, r, q)$ in Claim 16 (where we use the fact that, for $\alpha = 0, 1$, $\alpha(2 - \alpha) = \alpha$) we get the value of $\mathcal{A}'(s, r, 2)$.

To be able to compare $G'(s, r, 2)$ with $\mathcal{A}'(s, r, 2)$ we write $G'(s, r, 2) = G(s, r, 2) + \max\{0, s - r - d\} = G(s, r, 2) + s - r - d + \max\{0, r + d - s\}$. According to the notation of [BCCP24] let $B(s, r, 2) = G(s, r, 2) + s - r = \frac{(s-r)^2 + 3(s-r) + \beta(3-\beta)}{6}$. So we get the value of $G'(s, r, 2)$. ◇

**Claim 21** $\mathcal{A}'(s, r, 2) \subset \mathcal{A}'(s, r + 1, 2)$ and $\mathcal{G}'(s, r + 1, 2) \subset \mathcal{G}'(s, r, 2)$.

*Proof.* That follows from the fact that $\mathcal{A}(s, r, 2) \subset \mathcal{A}(s, r + 1, 2)$; $\mathcal{A}^s(s, r, 2) \subseteq \mathcal{A}^s(s, r + 1, 2)$; $\mathcal{G}(s, r + 1, 2) \subset \mathcal{G}(s, r, 2)$ and $\mathcal{G}^s(s, r + 1, 2) \subseteq \mathcal{G}^s(s, r, 2)$ ◇

Now, to characterize the anomalies we have to know when $\mathcal{A}'(s, r, 2) \le G'(s, r, 2)$ or equivalently when $\mathcal{A}(s, r, 2) \le B(s, r, 2) - d$. So, we should find the greatest integer $r$ such that $\mathcal{A}(s, r, 2) \le B(s, r, 2) - d$. However, the determination of this integer as a function of $C$ is not easy as we deal with integers. So, we will use the trick of working with real numbers. Furthermore $\alpha$ and $\beta$ are varying. However we note that $0 \le \alpha \le 1$ and $0 \le \beta(3 - \beta) \le 2$.

**Claim 22** For a real $x$ let $\tilde{A}(s, x, 2) = (x^2 - 2x)/4$ and $\tilde{B}(s, x, 2) = [(s - x)^2 + 3(s - x) + 2]/6$ Let $z$ denote the real number for which $\tilde{A}(s, z, 2) = \tilde{B}(s, z, 2) - d$; then $z = \sqrt{12C + 4} - 2s$.

*Proof.* We have $3(z^2 - 2z) = 2(s-z)^2 + 6(s-z) - 12d + 4$ or equivalently $z^2 + 4sz - 2s^2 - 6s + 12d - 4$. Solving the equation we get the value $z = -2s + \sqrt{6s^2 + 6s - 12d + 4} = -2s + \sqrt{12C + 4}$. ◇
**Theorem 23** Let $C = s(s+1)/2 - d$ with $0 \le d \le s-1$.

Let $n = 2s + r$, where $0 \le r \le s-1$ and let $r = 2a + \alpha$, where $0 \le \alpha \le 1$.

Let $\rho = \lfloor z \rfloor = \lfloor \sqrt{12C+4} \rfloor - 2s$.

For $r \le \rho$ the set of anomalies is $\mathcal{A}'(s, r, 2)$ and so the number of anomalies is $\mathcal{A}'(s, r, 2)$.

For $r \ge \rho+1$ the number of anomalies is $G'(s, r, 2)$ and the set of anomalies consists of the $G'(s, r, 2)$ first independent sets of $\mathcal{A}'(s, r, 2)$ in the greedy compatible optimal solution $S^*$.

**Proof.**

Let $\rho$ be the greatest integer $\le z$. So $\rho = \lfloor z \rfloor = \lfloor \sqrt{12C+4} - 2s \rfloor$

Now we distinguish two cases for an integer $r$:

* $r \le \rho$: Then, by Claim 21 $\mathcal{A}'(s, r, 2) \subset \mathcal{A}'(s, \rho, 2)$

In that case we will see that the set of anomalies is exactly $\mathcal{A}'(s, r, 2)$. Indeed, $\alpha(1-\alpha) \le 1$ implies $A(s, \rho, 2) \le \tilde{A}(s, \rho, 2) - 1/2$. As $\tilde{A}(s, x, 2)$ is increasing in $x$: $\tilde{A}(s, \rho, 2) \le \tilde{A}(s, z, 2)$. On the other side as $\tilde{B}(s, x, 2)$ is decreasing in $x$ we have $\tilde{B}(s, z, 2) \le \tilde{B}(s, \rho, 2)$ and, as $\beta(3-\beta) \le 2$, we have $\tilde{B}(s, z, 2) \le B(s, \rho, 2) - 1/3$. Using $\tilde{A}(s, z, 2) = \tilde{B}(s, z, 2) - d$ we get $A(s, \rho, 2) \le B(s, \rho, 2) - d - 5/6$. But as these values are integers and $5/6 < 1$ we get $A(s, \rho, 2) \le B(s, \rho, 2) - d$. Therefore, by Claim 21, for $r \le \rho$, $A(s, r, 2) \le A(s, \rho, 2) \le B(s, \rho, 2) - d \le B(s, r, 2) - d$ and so $A'(s, r, 2) \le G'(s, r, 2)$.

So for an $r \le \rho$ the set of anomalies is exactly $\mathcal{A}'(s, r, 2)$.

* $r \ge \rho+1$: Then, by Claim 21 $\mathcal{G}'(s, r, 2) \subset \mathcal{G}'(s, \rho+1, 2)$

Furthermore we note that as $z < \rho+1$:

$$B(s, \rho+1, 2) - d \le \tilde{B}(s, \rho+1, 2) - d < \tilde{B}(s, z, 2) - d = \tilde{A}(s, z, 2) < A(s, \rho+1, 2).$$

The first inequality follows from $\beta(3-\beta) \ge 0$, the second one from the decrease of the function $\tilde{B}(s, x, 2)$, the third one from the definition of $z$ and the last one from the increase of $\tilde{A}(s, x, 2)$.

So, for $r \ge \rho+1$, $G'(s, r, 2) \le G'(s, \rho+1, 2) < A'(s, \rho+1, 2) \le A'(s, r, 2)$. So the number of anomalies is for $r \ge \rho+1$ bounded from above by $G'(s, \rho+1, 2)$. Furthermore for $r = \rho+1$ the set of anomalies consists of $G'(s, \rho+1, 2)$ sets taken among the set $\mathcal{A}'(s, \rho+1, 2)$.

□

**Theorem 24** Let $C = s(s+1)/2 - d$ with $0 \le d \le s-1$. Let $\rho = \lfloor z \rfloor = \lfloor \sqrt{12C+4} \rfloor - 2s$ and let $\rho = 2a_\rho + \alpha_\rho$, where $0 \le \alpha_\rho \le 1$. Then, the maximum number of anomalies is bounded from above by

$$A'(s, \rho+1, 2) - 1 = \frac{\rho^2 - \alpha_\rho}{4} - 1 + \max\{0, \rho+1+d-s\}$$

For any $r$, there exists at least one greedy compatible optimal solution $S^*$ such that the maximum set of anomalies is included in the set $\mathcal{A}^s(s, \rho+1, 2) \cup \mathcal{A}(s, \rho+1, 2) - I^*$ where $I^*$ is the independent set $I(s+a_\rho, 1)$ if $\rho$ is even or $I(s+a_\rho, 2)$ if $\rho$ is odd. More precisely this set consists of

- the independent sets $\bigcup_{k=1}^{a_\rho-1} I(s+k, t)$, $1 \le t \le 2a_\rho+1-2k$ if $\rho = 2a_\rho$ is even

- the independent sets $\bigcup_{k=1}^{a_\rho-1} I(s+k, t)$, $1 \le t \le 2a_\rho+2-2k$ if $\rho = 2a_\rho+1$ is odd

- and if $\rho > s-d$ the $(\rho+1+d-s)$ independent sets $I(s, t)$ with $s-d+1 \le t \le \rho+1$.
**Proof.** The maximum number of anomalies is either $A'(s, \rho, 2)$ or $G'(s, \rho+1, 2)$. As $A'(s, \rho, 2) < A'(s, \rho+1, 2)$ and $G'(s, \rho+1, 2) < A'(s, \rho+1, 2)$ the maximum number of anomalies is bounded from above by $A'(s, \rho+1, 2) - 1$. We note that $\alpha_{\rho+1} = 1 - \alpha_{\rho}$ and so $A'(s, \rho+1, 2) - 1 = \frac{(\rho+1)^2-2(\rho+1)+1-\alpha_{\rho}}{4} - 1 + \max\{0, \rho+1+d-s\} = \frac{\rho^2-\alpha_{\rho}}{4} - 1 + \max\{0, \rho+1+d-s\}$.

Finally, let $I^*$ be the independent set $I(s+a_{\rho}, 1)$ if $\rho = 2a_{\rho}$ or $I(s+a_{\rho}, 2)$ if $\rho = 2a_{\rho}+1$. We note that $I^*$ appears in $A'(s, r, 2)$ when $r \ge \rho+1$ and does not appear in $A'(s, r, 2)$ when $r \le \rho$. So for any $r \le \rho$ the set of anomalies $A'(s, r, 2)$ is included in $A'(s, \rho+1, 2) - I^*$. Due to the strict inequality $G'(s, \rho+1, 2) < A'(s, \rho+1, 2)$, the set of the first $G'(s, \rho+1, 2)$ independent sets of $A'(s, \rho+1, 2)$ is included in $A'(s, \rho+1, 2)$ minus the last independent set in weight order.

For $\rho+1$ we will choose an order of type $T^+$ such that the set $I^*$ is ranked in the last position (which is always possible). For any solution $S^{*+}$ associated to such an order the first $G'(s, \rho+1, 2)$ independent sets of $A'(s, \rho+1, 2)$ are included in $A'(s, \rho+1, 2) - I^*$. If $r \ge \rho+1$ let us choose any order of type $T^+$ (and so any solution $S^{*+}$) such that the first $G'(s, r, 2)$ independent sets of $A'(s, r, 2)$ are exactly the same as those in the order taken for $\rho+1$. Then the first $G'(s, r, 2)$ independent sets of $A'(s, r, 2)$ are included in $A'(s, \rho+1, 2) - I^*$. $\square$

## 5 Load on arc $(i,i+1)$

One can note that when we take $C$ independent sets the load on each arc is at most $C$ and that this load is attained for the arcs in the middle. However on the arcs at the end of the paths it can be considerably less than $C$ leaving the possibility to add requests in the digraphs of type $Y$. Our aim is now to determine an upper bound on the load on the arcs at the end of the path $P_n$ in particular for the arc $e_i = (i, i+1)$ with $i \le s$. The load of the arc $e_i = (i, i+1)$ denoted $P_i(C, n)$ consists of two parts: the load due the requests of the greedy solution denoted $S_i(C, n)$ plus the load due to the anomalies. We will in fact determine an upper bound for a greedy compatible optimal solution $S^{opt}$ by computing the load due to the maximum set of anomalies described in Theorem 24. We will split this load in two parts : that due to the requests of size $s$ and that due the requests of size greater than $s$. We first give two general claims and will use them for the solution $S^{opt}$.

**Claim 25** Let $A_i^s(C, n)$ denote the load on the arc $(i, i+1)$ due to the requests of $A^s(s, r, 2)$. Then, for $1 \le i \le r$:

$$S_i(C, n) + A_i^s(C, n) = is - i(i-1)/2$$

*Proof.* In what follows $C$ (and so $s$ and $d$) and $n$ are given and so we omit the $C$ and $n$ and we shortly use $S_i$ instead of $S_i(C, n)$, $A_i^s$ instead of $A_i^s(C, n)$.

$S_i$ corresponds to the load on the arc $(i, i+1)$ due to all the requests of size $\le s-1$ plus $s-d$ requests of size $s$. We have two cases according $i$ is large or small.

If $i \le s-d$, then $S_i = is - i(i-1)/2$.

If $i \ge s-d$, then $S_i = i(s-1) - i(i-1)/2 + s - d$

On the other side as proved in theorem 18 if $r \le s-d$, $A^s(s, r, 2) = \emptyset$ while if $r \ge s-d$, $A^s(s, r, 2) = \bigcup_{t=s-d+1}^{r} I(s, t)$. In the second case the requests of $A^s(s, r, 2)$ cover only the arcs between $s-d+1$ and $r$. So we have:

If $i \le s-d$, then $A_i^s = 0$ and $S_i + A_i^s = is - i(i-1)/2$.

If $s-d < i \le r$ then $A_i^s = i - (s-d)$ and so $S_i + A_i^s = is - i(i-1)/2$. $\diamond$

**Claim 26** Let $M_i(r)$ denote the load on the arc $(i, i+1)$ due to the requests of $A^s(s, r, 2)$. If $1 \le i \le r$ then
$$ M_i(r) = \sum_{t=1}^{i} \lfloor (r-t)/2 \rfloor = \begin{cases} ir/2 - i(i+2)/4 & \text{if } i \text{ is even} \\ ir/2 - (i+1)^2/4 + \epsilon/2 & \text{where } \epsilon = 1 \text{ if } r \text{ is odd} \end{cases} $$

If $r-2 \le i \le s$, then $M_i(r) = A(s, r, 2) = (r^2 - 2r + \alpha_r)/4$

$$ \textit{Proof.} \text{ Recall that } \mathcal{A}(s,r,2) = \bigcup_{k=1}^{a} \bigcup_{l=1}^{r-2k} I(s+k,t) $$

If $r-2 \le i$ all the vectors of $\mathcal{A}(s, r, 2)$ have their first requests starting in a node $j \le r-2 \le i$. So, all these vectors load the arc $(i, i+1)$.

For $1 \le i \le r-2$ we can write

$$ \mathcal{A}(s,r,2) = \bigcup_{t=1}^{r-2\lfloor(r-t)/2\rfloor} \bigcup_{k=1}^{r-2k} I(s+k,t) $$

We note that all the vectors with $t \le i$ load the arc $(i, i+1)$. So

$$ M_i(r) = \sum_{t=1}^{i} \lfloor (r-t)/2 \rfloor $$

We get the formula of the claim by considering the 4 cases of parities of $r$ and $i$.

* $r$ even and $i$ even $M_i(r) = ir/2 - (1+1+2+2+...+i/2+i/2) = ir/2 - i(i+2)/4$

* $r$ even and $i$ odd $M_i(r) = ir/2 - (1+1+...+(i-1)/2+(i-1)/2+(i+1)/2) = ir/2 - (i+1)^2/4$

* $r$ odd and $i$ even $M_i(r) = ir/2 - [1+3+3+5...+(i-1)+(i+1)]/2 = ir/2 - i(i+2)/4$

* $r$ odd and $i$ odd $M_i(r) = ir/2 - [1+3+3+5...+(i-2)+i+i]/2 = ir/2 - (i^2+2i-1)/4$

The formula is also valid for $i = r-1$ and $i = r$ as there are no independent sets with $t = r-1$ or $t = r$ and $\lfloor (r-t)/2 \rfloor = 0$ we get $M_i(r) = A(s, r, 2)$. For example for $i = r$ $ir/2 - i(i+2)/4 = (r^2 - 2r + \epsilon)/4 = A(s, r, 2)$ ($\epsilon = 1$ if $i$ is odd). ◇

Let $\rho = \lfloor -2s + \sqrt{12C+4} \rfloor$. By Theorem 24 we know that there exists a greedy compatible optimal solution $S^{opt}$ such that the maximum set of anomalies is included in the set $\mathcal{A}^s(s, \rho + 1, 2) \cup \mathcal{A}(s, \rho + 1, 2) - I^*$ where $I^*$ is the independent set $I(s + a_\rho, 1)$ if $\rho = 2a_\rho$ or $I(s + a_\rho, 2)$ if $\rho = 2a_\rho + 1$. So for such a solution $S^{opt}$ using Claims 25 and 26 we can give an upper bound $P_i^m(C)$ (shortly denoted $P_i^m$) on the load of the arc $(i, i+1)$. The reader can check the values for $s = 10$ in Table 2.

**Theorem 27** Let $\mu = \lfloor \sqrt{12C+4} \rfloor$ and $\rho = \mu - 2s$. The maximum load for a greedy compatible optimal solution $S^{opt}$ on the arc $(i, i+1)$ ($i \le s$) is bounded by $P_i^m$ where:

If $i = 1$ $P_1^m = \mu/2 - 1$ if $\mu$ is even and $P_1^m = \mu/2 - 1/2$ if $\mu$ is odd.

If $i$ is even, $2 \le i \le \rho + 1$, $P_i^m = i\mu/2 - (3i^2 - 2i + 4)/4$

If $i$ is odd, $3 \le i \le \rho + 1$, $P_i^m = i\mu/2 - (3i^2 - 2i + 5)/4 + \epsilon/2$ where $\epsilon = 1$ if $\mu$ is even

If $i \ge 2$ and $i \ge \rho - 1$, $P_i^m \le \min\{C, is - i(i-1)/2 + \rho^2/4 - 1\}$

**Proof.** Let $\mu = \lfloor \sqrt{12C+4} \rfloor$. We have $\rho/2 = \mu/2 - s$ or $\mu/2 = \rho/2 + s$ and we note that $\rho$ and $\mu$ have the same parity.

We first deal with the case $i = 1$.

By claim 25 $S_1 + A_1^s = s$ and by claim 26 $M_i(\rho + 1) = \lfloor \rho/2 \rfloor$.
If $\rho$ is even, we delete the independent set $I^* = I(s + a_\rho, 1)$ that covers the arc $(1, 2)$ and so
$P_1^m = s + M_i(\rho + 1) - 1 = s + \rho/2 - 1 = \mu/2 - 1$.

If $\rho$ is odd, we delete the independent set $I^* = I(s + a_\rho, 2)$ that does not cover the arc $(1, 2)$ and so $P_1^m = s + M_i(\rho + 1) = s + (\rho - 1)/2 = (\mu - 1)/2$.

Now we consider the case where $2 \le i \le \rho + 1$. We note that the independent set $I^*$ covers the arc $(i, i+1)$ and so $P_i^m = S_i + A_i^s + M_i(\rho+1) - 1$.

If $i$ is even $M_i(\rho + 1) = i(\rho + 1)/2 - i(i + 2)/4$ and so $P_i^m = is - i(i - 1)/2 + i(\rho + 1)/2 - i(i + 2)/4 - 1$ that is $P_i^m = i\mu/2 - (3i^2 - 2i + 4)/4$

If $i$ is odd $M_i(\rho + 1) = i(\rho + 1)/2 - (i + 1)^2/4 + \epsilon/2$ where $\epsilon = 1$ if $\rho$ is even and so
$P_i^m = is - i(i - 1)/2 + i(\rho + 1)/2 - (i + 1)^2/4 + \epsilon/2 - 1$ that is $P_i^m = i\mu/2 - (3i^2 - 2i + 5)/4 + \epsilon/2$

If $i \ge \rho + 1$, then $M_i(\rho + 1) = A(s, \rho + 1, 2)$. So $P_i^m = is - i(i - 1)/2 + A(s, \rho + 1, 2) - 1$
where $A(s, \rho + 1, 2) = \frac{(\rho+1)^2 - 2(\rho+1) + \alpha_{\rho+1}}{4} \le \rho^2/4$.

Furthermore we have by construction the solution $S^*$ being feasible $P_i^m \le C$.

One can check that for $i = \rho - 1$ and $i = \rho$ the formula with the $\mu/2$ and that with $s$ are the same. $\square$

<table><thead><tr><th>C</th><th>μ</th><th>ρ</th><th>P<sub>1</sub><sup>m</sup></th><th>P<sub>2</sub><sup>m</sup></th><th>P<sub>3</sub><sup>m</sup></th><th>P<sub>4</sub><sup>m</sup></th><th>P<sub>5</sub><sup>m</sup></th><th>P<sub>6</sub><sup>m</sup></th><th>R<sub>1</sub></th><th>R<sub>2</sub></th><th>R<sub>3</sub></th><th>R<sub>4</sub></th><th>R<sub>5</sub></th><th>R<sub>6</sub></th><th>x</th></tr></thead><tbody><tr><td>46-47</td><td>23</td><td>3</td><td>11</td><td>20</td><td>28</td><td>35</td><td>41</td><td>46</td><td>11</td><td>10</td><td>9</td><td>8</td><td>7</td><td>1-2</td><td>6</td></tr><tr><td>48-51</td><td>24</td><td>4</td><td>11</td><td>21</td><td>30</td><td>37</td><td>43</td><td>48</td><td>11</td><td>10</td><td>9</td><td>8</td><td>7</td><td>3-6</td><td>6</td></tr><tr><td>52-55</td><td>25</td><td>5</td><td>12</td><td>22</td><td>31</td><td>39</td><td>45</td><td>50</td><td>12</td><td>11</td><td>10</td><td>9</td><td>8</td><td>3-5</td><td>6</td></tr></tbody></table>

<table><caption>Table 2: Values for $s = 10$</caption><thead><tr><th>C</th><th>y</th><th>N<sub>6</sub><sup>B</sup></th><th>L<sub>6</sub><sup>B</sup></th><th>N<sub>5</sub><sup>B</sup></th><th>L<sub>5</sub><sup>B</sup></th><th>N<sub>4</sub><sup>B</sup></th><th>L<sub>4</sub><sup>B</sup></th><th>N<sub>3</sub><sup>B</sup></th><th>L<sub>3</sub><sup>B</sup></th><th>N<sub>2</sub><sup>B</sup></th><th>L<sub>2</sub><sup>B</sup></th><th>N<sub>1</sub><sup>B</sup></th><th>L<sub>1</sub><sup>B</sup></th></tr></thead><tbody><tr><td>46-47</td><td>5</td><td>0</td><td>46</td><td>2</td><td>43</td><td>6</td><td>41</td><td>11</td><td>39</td><td>16</td><td>36</td><td>≤22</td><td>≤33</td></tr><tr><td>48-51</td><td>5</td><td>0</td><td>48</td><td>2</td><td>45</td><td>6</td><td>43</td><td>≤12</td><td>≤42</td><td>≤18</td><td>≤39</td><td>≤24</td><td>≤35</td></tr><tr><td>52-55</td><td>6</td><td>1</td><td>51</td><td>4</td><td>49</td><td>9</td><td>48</td><td>14</td><td>45</td><td>19</td><td>41</td><td>≤25</td><td>≤37</td></tr></tbody></table>

# 6 Proof of Theorem 3

We will now use the results of the preceding section to prove Theorem 3 and so, by the proof of Section 1, Theorem 2. In what follows $C = C_s - d$, where $C_s = s(s+1)/2$ and $0 \le d \le s - 1$ is fixed and we will omit $C$ when the context is clear. We consider an $Y$-tree $Y = (A, (a, b), B \cup B')$. We let $A = (a_{n_A}, a_{n_{A-1}}, \dots, a_2, a_1 = a)$ and $B = (b = b_1, b_2, \dots, b_{n_B-1})$ and $B' = (b = b'_1, b'_2, \dots, b'_{n_{B'-1}})$ and we suppose $n_A, n_B, n_{B'} \ge s$. We put on the dipaths $A, B, B'$ the requests of a greedy compatible optimal solution $S^{opt}$ (see Theorem 24). Then we will add $C$ new requests containing the arc $(a = a_1, b = b_1)$ between vertices of the dipath $A$ and vertices of the two dipaths $B$ and $B'$ in such a way that the load on the arcs of $A, B, B'$ will be at most $C$. The load on the arcs of the other paths is by definition at most $C$ and so the theorem will be proved.

We will use the upper-bound $P_i^m$ on the load of the arc $(i, i+1), (1 \le i \le s)$ of a dipath with a greedy compatible optimal solution $S^{opt}$ given in Theorem 27.

The $C$ new requests will join the vertices $a_i$ of $A, 1 \le i \le x \le s$ to the same or almost the same number of vertices of $B$ and $B'$. Let $R_i$ (abbreviation of $R_i(C)$) denote the number of new requests starting in $a_i$.
The load on the arc $(a_{i+1}, a_i)$ due to the new requests is $N_i^A = C - \sum_{k=1}^{k=i} R_k$ and so the total load $L_i^A$ on the arc $(a_{i+1}, a_i)$ satisfies $L_i^A \le P_i^m + C - \sum_{k=1}^{k=i} R_k$. In order that the load on the arcs of the dipath A, $L_i^A \le C$, the $R_i$ should satisfy

$$ \text{For all } i \quad \sum_{k=1}^{k=i} R_k \ge P_i^m \quad (*) $$

The value $x$ will be the smallest integer such that $\sum_{k=1}^{k=x} R_k \ge C$ and so there are no requests starting from a node $a_i$ with $i > x$.

Ideally we want to choose for $R_i$ the integers reaching equality in (*) that is $R_1 = P_1^m$ and for $i \ge 1$, $R_i = P_i^m - P_{i-1}^m$. That is what we did for $s \le 5$ in Table 3 in the introduction. We also note that the values depend of the parity of $\mu$ and $i$ and also of the position of $i$ compared to $\rho$.

So, in what follows we suppose $s \ge 6$ and we choose the following $R_i$ (slightly greater than the ideal values) in order to ease the computation and the proofs.

**Definition 28** Let $x-1$ be the greatest integer such that $\sum_{k=1}^{x-1} (R_1^m - k + 1) < C$ then:

* if $i \le x-1$, $R_i = R_1 - i + 1$ where $R_1 = P_1^m = \mu/2 - 1$ if $\mu$ is even and $\mu/2 - 1/2$ else

* $R_x = C - \sum_{k=1}^{x-1} R_1^m - k + 1$

* if $i > x$, $R_i = 0$

**Property 29** Inequality (*) is satisfied by the chosen $R_i$.

**Proof.** If $i \ge x$ there is nothing to prove as $\sum_{k=1}^{k=i} R_k = C$ and $P_i^m \le C$.

If $i=1$, $R_1 = P_1^m$ and so inequality is satisfied.

Otherwise we note that $R_1 \ge (\mu - 1)/2$ and so $\sum_{k=1}^{k=i} R_k \ge i\mu/2 - i^2/2$.

We distinguish two cases:

If $i \le \rho + 1$, $P_i^m \le i\mu/2 - (3i^2 - 2i + 3)/4$. Then the inequality follows from the fact that $(3i^2 - 2i + 3)/4 \ge i^2/2$ or equivalently $i^2 - 2i + 3 \ge 0$ (always true).

If $i > \rho + 1$, $P_i^m = i\rho + (i - i(1)/2 + \rho^2/4 - 1) = i\mu/2 - i\rho/2 - i(1)/2 + \rho^2/4 - 1$ (as $s = (\mu - \rho)/2$). So we have to prove that $i\rho/2 - i/2 - \rho^2/4 + 1 \ge 0$ or as $i \ge \rho + 1$ that $(\rho + 1)(\rho - 1) - \rho^2/2 + 2 \ge 0$ that is $\rho^2/2 + 1 \ge 0$ which is always true. $\square$

**Claim 30** The value $x$ satisfies $2 \le x \le s - 1$.

**Proof.** We $R_1 \le (\mu - 1)/2 = (\sqrt{12C + 4} - 1)/2 < C$; indeed it follows from $12C + 4 \le 4C^2 + 4C + 1$ when $C \ge 3$. So $x$ is well defined and $x \ge 2$.

Furthermore $x \le s - 1$; indeed we have $\sum_{k=1}^{k=s} R_k \ge (s - 1)\mu/2 - (s - 1)^2/2$ so it suffices to prove that $f(C) = (s - 1)\sqrt{3C + 1} - (s - 1)^2/2 - C \ge 0$. We have for a given $s$, $f'(C) \le 0$ and so $f(C)$ is decreasing and as $C > s(s - 1)/2 > (s - 1)^2/2$ it suffices to prove that $f((s - 1)^2 \ge (\sqrt{3/2} - 1)(s - 1)^2 > 0$ which is always true $\diamond$

As inequality (*) is satisfied the load on the arcs of the dipath A satisfies $L_i^A \le C$. Furthermore the load on $(a_1, b_1)$ is exactly $C$. It remains to show that with the chosen values of $R_i$ the load on the arcs of B and $B'$ is also bounded by $C$.

We choose to join $a_i$ to $b = b_1$, the $b_j$ with $2 \le j \le \lceil (R_i + 1)/2 \rceil$ and the $b'_j$ with $2 \le j \le \lceil (R_i + 1)/2 \rceil$. With this choice, the load of $(b_j, b_{j+1})$ is always greater than or equal to that of
$(b'_j, b'_{j+1})$) and so we will only compute the load $L_j^B$ on the arc $(b_j, b_{j+1})$ with $j \ge 1$. We have $L_j^B = P_j^m + N_j^B$, where $N_j^B$ denote the load on the arc $(b_j, b_{j+1})$ due to the new requests. We will now show with various claims that $L_j^B \le C$ so proving Theorem 2.

**Claim 31** Let $\mu = 4y + 1 + \nu$ with $0 \le \nu \le 3$ and $\epsilon = 1$ if $\nu = 2, 3$ and $0$ otherwise. So, $R_1 = 2y + \epsilon$ and the requests issued from $a_{2k+1}$ (with $1 \le 2k+1 \le x$) end in $b_j$ with $2 \le j \le y+1-k$ and the requests issued from $a_{2k}$ (with $2 \le 2k \le x$) end in $b_j$ with $2 \le j \le y+1-k+\epsilon$

*Proof.* We have $\lceil(R_1+1)/2\rceil = y$ and $\lceil(R_{2k+1}+1)/2\rceil = y-k+1$ and so the requests issued from $a_{2k+1}$ (with $1 \le 2k+1 \le x$) end in $b_j$ with $2 \le j \le y+1-k$. We have $\lceil(R_2+1)/2\rceil = y+\epsilon$ and $\lceil(R_{2k}+1)/2\rceil = y+\epsilon-k$ and the requests issued from $a_{2k}$ (with $2 \le 2k \le x$) end in $b_j$ with $2 \le j \le y+1-k+\epsilon$ ◇

Table 2 gives the values of $y$, $N_j^B$ and $L_j^B$ for $s = 10$.

**Corollary 32** If $j \ge y+1$, then $L_j^B \le C$

*Proof.* By Claim 31 there are no new requests loading the arc $(b_j, b_{j+1})$ with $j \ge y+1$ and so for these arcs the load $L_j^B = P_j^m \le C$. □

**Claim 33** $L_j^B \le C$

*Proof.* By Claim 31 there are $1+\epsilon$ requests loading the arc $(b_j, b_{j+1})$ namely one issued from $a_1$ and when $\nu = 2, 3$ (that is $\epsilon = 1$) one issued from $a_2$. Said otherwise $N_j^B = 1+\epsilon$.

First we claim that $y \ge \rho-1$. Indeed $y \ge \mu/4-1$. So it suffices to prove that $\mu/4-1 \ge \mu-2s-1$ or equivalently that $8s \ge 3\mu$, that is $64s^2 \ge 9\mu^2 = 9(12C+4)$. As $C \le (s^2+s)/2$ it suffices to prove that $64s^2 \ge 54s^2+54s+36$ which is true when $s \ge 6$ (our hypothesis).

Therefore by Theorem 27 $P_j^m = ys - y(y-1)/2 + \rho^2/4 - 1$ and

$$L_j^B = P_j^m + N_j^B \le ys - y(y-1)/2 + \rho^2/4 + \epsilon$$

We have $y = (\mu-1-\nu)/4$ and $\rho = \mu-2s$ and $C = (\mu^2-4)/12$. Multiplying by 12 we have to prove that $\mu^2-4 \ge 3(\mu-1-\nu)s - 3(\mu-\nu-1)(\mu-\nu-5)/8 + 3(\mu^2+4s^2-4\mu s) + 12\epsilon$ that is

$$-13\mu^2/8 - 12s^2 + 9\mu s + 3s - 9\mu/4 + (3s - 3\mu/4)\nu - 4 - 12\epsilon + 3(\nu+1)(\nu+5)/8 \ge 0$$

For a given $\mu$, the first member is decreasing in $s$. As $C \ge s(s-1)/2$ we have $\mu^2 \ge 6s^2 - 6s + 10 \ge 6(s - 1/2)^2$ and $s \le \mu\sqrt{6}/6 + 1/2$. So, it suffices to prove the inequality for $s = \mu\sqrt{6}/6 + 1/2$ that is:

$$(-13/8 - 2 + 3\sqrt{6}/2)\mu^2 + (-2\sqrt{6} + 9/2 + \sqrt{6}/2 - 9/4)\mu - 3 + 3/2 - 4 - 12\epsilon + 15/8 + g(\nu) \ge 0$$
where $g(\nu) = (\sqrt{6}/2 - 3/4)\mu\nu + 3\nu/2 + 3\nu^2/8 + 9\nu/4$ or

$$0.0492\mu^2 - 1.4242\mu - 3.625 - 12\epsilon + (0.4747\mu + 3\nu/8 + 15/4)\nu \ge 0$$

If $\nu = 0$ the inequality becomes $0.0492\mu^2 - 1.4242\mu - 3.625 \ge 0$ and is satisfied for $\mu \ge 33$.

If $\nu = 1$ the inequality becomes $0.0492\mu^2 - 0.9495\mu + 0.5 \ge 0$ and is satisfied for $\mu \ge 22$.

If $\nu = 2$ the inequality becomes $0.0492\mu^2 - 0.4747\mu - 6.625 \ge 0$ and is satisfied for $\mu \ge 19$.

If $\nu = 3$ the inequality becomes $0.0492\mu^2 - 1 \ge 0$ and is satisfied for $\mu \ge 8$.

So $L_j^B \le C$ if $\mu \ne 4, 5, 7, 9, 11, 13, 15, 17, 18, 21, 25, 29, 6, 10, 14$

We already did in the introduction the cases $s \le 5$ that is $C \le 15$ or $\mu \le 13$. For the remaining case we do exact computations using $L_j^B = P_j^m + N_j^B \le ys - y(y-1)/2 + \rho^2/4 + \epsilon$
If $\mu = 29, y = 7, 70 \le C \le 74, s = 12, \rho = 5$ and $L_y^B \le 69 < C$

If $\mu = 25: y = 6, 52 \le C \le 55, s = 10, \rho = 5$ and $L_y^B \le 51 < C$

If $\mu = 21: y = 5, 37 \le C \le 40, s = 9, \rho = 3$ and $L_y^B \le 37 \le C$

If $\mu = 17: y = 4, 24 \le C \le 26, s = 7, \rho = 3$ and $L_y^B \le 24 \le C$

If $\mu = 18: y = 4$, either $27 \le C \le 28, s = 7, \rho = 4$ and $L_y^B \le 26 \le C$ or $C = 29, s = 8, \rho = 2$ and $L_y^B \le 27 \le C$

If $\mu = 14: y = 3, 16 \le C \le 18, s = 6, \rho = 2$ and $L_y^B \le 16 \le C$

If $\mu = 15: y = 3, 19 \le C \le 20, s = 6, \rho = 3$ and $L_y^B \le 18 \le C$ ($\epsilon = 1$)

In summary in all the cases $L_y^B \le C$.

◇

**Claim 34** If $j \le y$, then $L_y^B < C$.

*Proof.* To finish we will prove that $L_y^B \le C$ for any $j < y$ by induction on decreasing $j$. That is true as we have seen for $j = y$. We will prove that if it is true for $j \ge 2$ it is also true for $j - 1$ by proving the inequality

$$P_{j-1}^m + N_{j-1}^B \le P_j^m + N_j^B$$

That implies that the load is decreasing when $j$ decreases and so is always bounded by $L_y^B$ which is at most $C$ by Claim 33.

On one side $N_{j-1}^B - N_j^B$ corresponds to the number of requests ending exactly in $j$. By Claim 31, we have $3 + \epsilon + 2k$ requests ending in $y - k$ ($\epsilon = 1$ if $\nu = 2, 3$ and $0$ if $\nu = 0, 1$) namely those issued from $a_i$ with $1 \le i \le 3 + \epsilon + 2k$. Therefore $N_{j-1}^B - N_j^B \le 2y - 2j + 3 + \epsilon$.

On the other side using the values of Theorem 27 we have to prove that $P_j^m - P_{j-1}^m \ge 2y - 2j + 3 + \epsilon$. We distinguish two cases.

If $j \le \rho + 1$, we have $P_j^m - P_{j-1}^m = \mu/2 - (6j - 5 + \delta - \delta')/4$ where $\delta = 0$ and $\delta' = 1$ or $-1$ if $i$ is even or $\delta' = 0$ and $\delta = 1$ or $-1$ if $i$ is odd. So if $j \le \rho + 1$ we always have $P_j^m - P_{j-1}^m \ge \mu/2 - (3j - 3)/2$. In that case we have to prove that $\mu/2 - (3j - 3)/2 \ge 2y - 2j + 3 + \epsilon$ or as $\mu \ge 4y + 1 + 2\epsilon$ that $j/2 \ge 1$ which is true as $j \ge 2$

If $j \ge \rho+1$, then $P_j^m - P_{j-1}^m = s-j+1$ and so we have to prove that $s-j+1 \ge 3+2y-2j+\epsilon$. As $j \ge \rho+1$ it suffices to check that $s \ge 2y - \rho + 1 + \epsilon$. As $2s = \mu - \rho$ we have to check that $\mu - \rho \ge 4y - 2\rho + 2 + 2\epsilon$ or as $\rho \ge 1$, that is $\mu \ge 4y + 1 + 2\epsilon$ which is always true.

◇

# 7 Extensions

We can relax the constraint on the number of vertices. Indeed the proof for the $Y$-tree given above works as soon as $n_A \ge x$ and $n_B, n_{B'} \ge y$. We know by Claim 30 that $x \le s - 1$. In fact $x$ satisfies $x\mu/2 - x^2/2 = C$ (see proof of Claim 29) and so as $C$ is of order $s^2/2$ and $\mu$ of order $\sqrt{6}s$, $x$ is of order $(\sqrt{6} - \sqrt{2})s/2$ value a little above $s/2$. As $\mu$ is of order $\sqrt{6}s$, $y$ is of order $\sqrt{6}s/4$ value a little above $0.61s$.

Furthermore if there are no anomalies (or at least if $A(s, r, 2)$ is empty) the proof works as soon as $n_A, n_B, n_{B'} \ge \lceil (s+1)/2 \rceil$. We recall that in this case the load of the arc $(i, i+1)$ of a dipath is by Claim 25 bounded by $is - i(i-1)/2$. If $C = C_s$ the new requests will join each vertex $A_i$ with $1 \le i \le \lfloor (s+1)/2 \rfloor$ to the vertex $b$ and the vertices $b_j, b'_j$ with $2 \le j \le \lceil (s+1)/2 \rceil$. If $s$ is odd the number of new requests is $((s+1)/2)s = C_s$ and if $s$ is even $(s+1)s/2 = C_s$. So the load of $(a = a_1, b = b_1)$ is $C_s$. The load on the arc $(a_{i+1}, a_i)$ due to these new requests is bounded by $C_s - is$ and so the total load is at most $C_s - i(i-1)/2 \le C_s$. If $s$ is odd the load on the arc $(b_j, b_{j+1})$ (or $(b'_j, b'_{j+1})$) with $1 \le j \le \lceil (s+1)/2 \rceil - 1$ due to these new requests is
($\frac{s+1}{2}$)($\frac{s+1}{2}$ - j) = C_s - $\frac{s^2-1}{4}$ - $\frac{(s+1)j}{2}$ and the total load is C_s - ($\frac{s-1}{2}$)($\frac{s+1}{2}$ - j) - $\frac{j(j-1)}{2}$ ≤ C_s as j ≤ (s + 1)/2. If s is even the load due to the new requests is ($\frac{s}{2}$)($\frac{s+2}{2}$ - j) = C_s - $\frac{s^2}{4}$ - $\frac{sj}{2}$ and the total load is C_s - ($\frac{s}{2}$)($\frac{s}{2}$ - j) - $\frac{j(j-1)}{2}$ ≤ C_s as j ≤ s/2.

If $C = C_s - d$, we delete $d$ new requests joining $a_{\lfloor(s+1)/2\rfloor}$ to the $b_j$ and $b'_j$ with $j \ge \lceil(s+1)/2\rceil - \lfloor d/2\rfloor$. The load on the arc $(a, b)$ is $C$ and a careful computation shows that the total load on the other arcs is still bounded by $C$ as soon as $s \ge 5$.

The role of the trunk is important in the proof of Theorem 2. We can extend the determination of the maximum number of requests for oriented trees having many trunks obtained by gluing on a Fig-Tree one or more other Fig-Trees.

More precisely let us define a **Generalized Fig-Tree** GF = ($T, A, B, C$) as follows. In such a tree there are

a set $T$ of $k$ special arcs called trunks $T = \cup(a_h, b_h), 1 \le h \le k$.

a set $A$ of dipaths of length at least $s$ joining a vertex with in-degree 0 to some $a_h$;

a set $B$ of dipaths of length at least $s$ joining some $b_h$ to a vertex with out-degree 0;

a set $C$ of dipaths of length at least $2s$ joining some $a_h$ to a $b'_h$.

As we want to have an oriented tree we impose that the dipaths of $C$ do not form a cycle.

Furthermore, to be able to use the results on Fig-Trees, we also impose that in the oriented tree the in-degree of $a_h$ and the out-degree of $b_h$ satisfy:

$$d^{+}(a_h) = 1; d^{-}(b_h) = 1; d^{-}(a_h) + d^{+}(b_h) \ge 3.$$

We note that if there is only one trunk we get a Fig-Tree. Theorem 2 can be extended as follows:

**Theorem 35** Let $C \ge 3$ and let GF = ($T, A, B, C$) be a Generalized Fig-Tree with $k$ trunks. Then the maximum number of requests $T(C, F)$ that can be groomed in $F$ is:

$$T(C, F) = kC + T(C, A) + T(C, B) + T(C, C)$$

**Proof.** Clearly the value of the second member is an upper-bound as each trunk can be covered by at most $C$ requests. The bound is attained by putting on each dipath of $A, B$ and $C$ the maximum number of requests. Then we note that according to the conditions on the in and out-degrees each trunk is part of a Fig-Tree and so we can add $C$ requests covering this trunk by the proof of Theorem 2. $\square$

We could like lower the constraints on the number of vertices of a Fig-Tree by letting the vertices of $A$ and $B$ be only $\ge y$ (or $\ge \lceil(s+1)/2\rceil$ if there are no anomalies) and those of $C$ be only $\ge 2y$ (or $\ge s+2$) if there are no anomalies).

# 8 Oriented Spiders

In this section we consider another class of oriented trees called (oriented) Spider-Trees. A Spider-Tree $S = (A, c, B)$ consists of a set $A$ of dipaths ending in a vertex $c$, plus a set $B$ of dipaths starting in the vertex $c$ (see Figure 2). The simplest Spider-Trees (not a dipath) are the $Y$-tree and the $\perp$-tree previously considered. The $Y$-tree $(A, (a, b), B \cup B')$ is exactly the Spider-Tree $(A \cup (a, b), b, B \cup B')$. The $\perp$-tree $(A \cup A', (a, b), B)$ is exactly the Spider-Tree $(A \cup A', a, (a, b) \cup B)$ (see section 2).

To the dipath $A^i$ of $A$, we associate the dipath $\overline{A^i}$ obtained by deleting the last arc $(a_1^i, c)$ of $A^i$. If $A = \cup A^i$, we define $\overline{A} = \cup \overline{A^i}$. Similarly, if $B = \cup B^j$, we define $\overline{B} = \cup \overline{B^j}$ where $\overline{B^j}$ is obtained by deleting the first arc $(c, b_1^j)$ of $B^j$.
**Proposition 36** Let $T(C, S)$ be the maximum number of requests that can be groomed in a Spider-Tree $S = (\mathcal{A}, c, \mathcal{B})$ with $|\mathcal{A}| = \alpha$ and $|\mathcal{B}| = \beta$. Then:

$$T(C, S) \leq \min\{\alpha C + T(C, \bar{\mathcal{A}}) + T(C, \mathcal{B}) \; ; \; \beta C + T(C, \mathcal{A}) + T(C, \bar{\mathcal{B}})\}$$

**Proof.** The requests inside $\bar{\mathcal{A}}$ and $\mathcal{B}$ are disjoint and in number $T(C, \bar{\mathcal{A}}) + T(C, \mathcal{B})$. Those between a vertex in $\bar{\mathcal{A}}$ and a vertex in $\mathcal{B}$ use the arcs $(a_1^i, c)$ and so their number is at most $\alpha C$ and so we get the first upperbound. The second upper-bound is obtained by interchanging the role of $\mathcal{A}$ and $\mathcal{B}$. $\square$

If $\alpha = 1$ and $\beta = 2$ the Spider-Tree $(A \cup (a, b), b, B \cup B')$ is the $Y$-tree $(A, (a, b), B \cup B')$ and $\overline{A \cup (a, b)} = A$. So by Theorem 3 the first upper-bound $C + T(C, A) + T(C, B) + T(C, B')$ is attained.

Similarly if $\alpha = 2$ and $\beta = 1$ the Spider-Tree $(A \cup A', a, (a, b) \cup B)$ is the $\perp$-tree $(A \cup A', (a, b), B)$ and $(\overline{a, b} \cup \overline{B} = B)$ and the second upper-bound $C + T(C, A) + T(C, A') + T(C, B)$ is attained.

<figure><img src="image_6.png" /><figcaption>Figure 2: Examples of Spiders where $A^i$ and $B^i$ are dipaths.</figcaption></figure>

We can generalize these results as follows

**Theorem 37** Let $T(C, S)$ be the maximum number of requests that can be groomed in a Spider-Tree $S = (\mathcal{A}, c, \mathcal{B})$ with $|\mathcal{A}| = \alpha$ and $|\mathcal{B}| = \beta$ and where the dipaths of $\mathcal{A} \cup \mathcal{B}$ have a number of vertices $\geq (s+1)/2$. Then

$$\text{If } \alpha \leq 2\beta \quad T(C, S) = \alpha C + T(C, \bar{\mathcal{A}}) + \mathcal{T}(C, \mathcal{B})$$

$$\text{If } \beta \leq 2\alpha \quad T(C, S) = \beta C + T(C, \mathcal{A}) + T(C, \bar{\mathcal{B}})$$

**Proof.** Suppose $\alpha \leq 2\beta$, then the Spider-tree $S = (\mathcal{A}, c, \mathcal{B})$ is the union of $\alpha$ $Y$-trees namely $(\overline{\mathcal{A}^i}, (a_1^i, c), B^{2i-1} \cup B^{2i})$ ($1 \leq i \leq \alpha$). On the $i$th of these $Y$-tree we can put by Theorem 3 $C + T(C, \overline{\mathcal{A}^i}) + T(C, B^{2i-1}) + T(C, B^{2i})$ requests. Then we put the maximum number of requests $T(C, B^j)$ on each $B^j$ of $\mathcal{B}$ with $2\alpha < j \leq \beta$. So altogether we can put $\alpha C + T(C, \overline{\mathcal{A}}) + T(C, \mathcal{B})$
requests therefore reaching the upper-bound and proving the Theorem. Similarly we can prove the second part of the Theorem by interchanging the role of A and B and using ⊥-trees consisting of one path of A and two paths of $\overline{B}$.

<figure><img src="image_7.png" /></figure>

We conjecture that the lower bound is always attained

**Conjecture 38** Let $S = (A, c, B)$ be a Spider-Tree with $|A| = \alpha$ and $|B| = \beta$ and where the dipaths of $A \cup B$ have a number of vertices $\ge (s+1)/2$. Then the maximum number of requests that can be groomed in $S$ is:

$$T(C, S) = \min\{\alpha C + T(C, \overline{A}) + T(C, B) ; \beta C + T(C, A) + T(C, \overline{B})\}$$

The first unsolved case is $\alpha = \beta = 2$. Such a Spider-Tree $A \cup A', c, B \cup B'$ is called an X-Tree (see Figure 2). Suppose that the dipaths $A, A', B, B'$ have all the same number of vertices $n \ge (s+1)/2$. The two upper bounds are equal and so

$$T(C, S) \le 2[C + T(C, n) + T(C, n - 1)]$$

The conjecture says that this bound is attained. A lower bound is obtained by putting the maximum number of requests on the dipaths $A \cup B$ and $A' \cup B'$ which have each $2n - 1$ vertices and so

$$T(C, S) \ge 2T(C, 2n - 1)$$

If $T(C, 2n - 1) = C + T(C, n) + T(C, n - 1)$ the conjecture is true. That is the case for example if $C = C_s$ and there are no anomalies for $n$ and $n - 1$; indeed $T(C, n) = sn - C_s$; $T(C, n - 1) = s(n - 1) - C_s$ and $T(C, 2n - 1) = s(2n - 1) - C_s = C + T(C, n) + T(C, n - 1)$.

But it is not always the case. For example if $C = 10$ ($s = 4$) and $n = 11$: $T((10, 21) = 74$ while $T(10, 11)+T(10, 10)+10 = 35+30+10 = 75 > 74$. But in that case we are able to put $2 \times 75$ requests, so verifying the conjecture. Let $A = a_{11}, a_{10}, \dots, a_2, a_1, c$; $A' = a'_{11}, a'_{10}, \dots, a'_2, a'_1, c$; $B = c, b_1, b_2, \dots, b_{10}, b_{11}$; $B' = c, b'_1, b'_2, \dots, b'_{10}, b'_{11}$. We use the following trick. Consider the path $A \cup B$ with 21 vertices. We put the 74 requests of length $\le 4$ of the greedy solution. We delete the requests $(a_4, c)$, $(a_8, a_4)$ and $(c, b_4)$, $(b_4, b_8)$. Then we add the requests $(a_5, a_1)$, $(a_9, a_5)$ and $(b_1, b_5)$, $(b_5, b_9)$. Doing so the loads of the arcs $(a_1, c)$ and $(c, b_1)$ have decreased by 1 (the value is now 9) while the load of the arcs $(a_9, a_8)$ and $(b_8, b_9)$ have increased by 1 from 9 to 10. So we have obtained a feasible solution with still 74 requests. We do the same construction for $A' \cup B'$. Finally we now have room to add to these 148 requests the two requests $(a_1, b'_1)$ and $(a'_1, b_1)$ keeping a maximum load on each arc of $C = 10$. All together we have the desired solution with 150 requests.

We have been able to check the conjecture for small values of $C$ with the same kind of constructions.

# 9 Conclusion

In this article we have solved the MARPG problem for various classes of oriented trees in particular for the class of Fig-Trees. This class include Y-Trees and ⊥-trees which are oriented spiders with 3 legs. We have proposed a conjecture for general oriented Spider-trees. To prove our main theorem we have revisited the MARPG problem for directed paths. We have characterized the set of requests in optimal solutions and give bounds on the maximum load of an arc of the dipath obtaining results which are interesting in themselves and useful to compute the cutwidth of a graph.
References

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

[BBC07] Jean-Claude Bermond, Laurent Braud, and David Coudert. Traffic Grooming on the Path. Theoretical Computer Science, 384(2-3):139-151, 2007.

[BBG+97] Bruno Beauquier, Jean-Claude Bermond, Luisa Gargano, Pavol Hell, Stéphane Pérennes, and Ugo Vaccaro. Graph problems arising from wavelength-routing in all-optical networks. In WOCS 1997-2nd Workshop on Optics and Computer Science-11th International Parallel Processing Symposium, 1997.

[BC07] Jean-Claude Bermond and Michel Cosnard. Minimum number of wavelengths equals load in a DAG without internal cycle. In IEEE, editor, IPDPS07, pages 1-10, Long beach, CA, United States, March 2007.

[BCCH23] Jean-Claude Bermond, Michel Cosnard, David Coudert, and Frédéric 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.

[BCCP24] Jean-Claude Bermond, Michel Cosnard, David Coudert, and Stephane Perennes. Maximum number of requests on a path with a given grooming factor. Technical report, hal-04736088, October 2024. A preliminary version was presented at the Advanced International Conference on Telecommunications (AICT), Le Gosier, Guadeloupe, France, 2006, IEEE.

[BGK+06] Jean-Claude Bermond, Jerome Galtier, Ralf Klasing, Nelson Morales, and Stephane Perennes. Hardness and approximation of gathering in static radio networks. Parallel Processing Letters, 16(02):165-183, 2006.

[BKK+09] Vincenzo Bonifaci, Ralf Klasing, Peter Korteweg, Leen Stougie, and Alberto Marchetti-Spaccamela. Data gathering in wireless networks. In Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless and Ad Hoc Networks, pages 357-377. Springer, 2009.

[BKM+13] Jean-Claude Bermond, Ralf Klasing, Nelson Morales, Stéphane Pérennes, and Patricio Reyes. Gathering radio messages in the path. Discrete Mathematics, Algorithms and Applications, 5(01):1350004, 2013.

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

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

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

[DR02] Rudra Dutta and George N Rouskas. Traffic grooming in wdm networks: Past and future. IEEE network, 16(6):46-56, 2002.

[EJ98] 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.

[EJ01] Thomas Erlebach and Klaus Jansen. The complexity of path coloring and call scheduling. Theoretical Computer Science, 255(1-2):33-50, 2001.

[EJK+99] Thomas Erlebach, Klaus Jansen, Christos Kaklamanis, Milena Mihail, and Pino Persiano. Optimal wavelength routing on directed fiber trees. Theoretical Computer Science, 221(1-2):119-137, 1999.

[EV06] Thomas Erlebach and Danica Vukadinović. Path problems in generalized stars, complete graphs, and brick wall graphs. Discrete Applied Mathematics, 154(4):673-683, 2006. Efficient Algorithms.
[GHP97] Luisa Gargano, Pavol Hell, and Stephane Perennes. Colouring paths in directed symmetric trees with applications to wdm routing. In *Automata, Languages and Programming: 24th International Colloquium, ICALP'97 Bologna, Italy, July 7-11, 1997 Proceedings 24*, pages 505-515. Springer, 1997.

[GV00] Luisa Gargano and Ugo Vaccaro. Routing in all-optical networks: Algorithmic and graph-theoretic problems. *Numbers, Information and Complexity*, pages 555-578, 2000.

[HDR06] Shu Huang, Rudra Dutta, and George N Rouskas. Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms. *IEEE Journal on Selected Areas in Communications*, 24(4), 2006.

[HKP+05] Juraj Hromkovič, Ralf Klasing, Andrzej Pelc, Peter Ruzicka, and Walter Unger. *Dissemination of information in communication networks: broadcasting, gossiping, leader election, and fault-tolerance*. Springer Science & Business Media, 2005.

[Kla98] Ralf Klasing. Methods and problems of wavelength-routing in all-optical networks. In *Presented as invited talk at the MFCS'98 Workshop on Communications*. Technical Report CS-RR-348, Department of Computer Science, University of Warwick, September, 1998.

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

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