| Abstract: | Motivated by wavelength division multiplexing in all-optical networks, we consider the problem of finding a set of paths from a fixed source to a multiset of destinations, which can be coloured by the fewest number of colours so that paths of the same colour do not share an arc. We prove that this minimum number of colours (wavelengths) is equal to the maximum number of paths that share one arc (the load), minimized over all sets of paths from the source to the destinations. We do this by modeling the problems as network flows in two different networks and relating the structure of their minimum cuts. The problem can be efficiently solved (paths found and coloured) using network flow techniques. |
| Abstract: | Traffic grooming is a central problem in optical networks. It refers to packing low rate signals into higher speed streams, in order to improve bandwidth utilization and reduce network cost. In WDM networks, the most accepted criterion is to minimize the number of electronic terminations, namely the number of SONET Add-Drop Multiplexers (ADMs). In this article we focus on ring and path topologies. On the one hand, we provide an inapproximability result for Traffic Grooming for fixed values of the grooming factor g, answering authorrmatively the conjecture of Chow and Lin (Networks, 44:194-202, 2004 ). More precisely, we prove that Ring Traffic Grooming for fixed $g\leq 1$ and Path Traffic Grooming for fixed $g \leq 2$ are Apx-complete. That is, they do not accept a PTAS unless P = NP. Both results rely on the fact that finding the maximum number of edge-disjoint triangles in a tripartite graph (and more generally cycles of length $2g + 1$ in a $(2g + 1)$-partite graph of girth $2g + 1$) is Apx-complete. On the other hand, we provide a polynomial-time approximation algorithm for Ring and Path Traffic Grooming, based on a greedy cover algorithm, with an approximation ratio independent of $g$. Namely, the approximation guarantee is ${\mathcal O} (n^{1/3}\log^2(n))$ for any $g\leq 1$, $n$ being the size of the network. This is useful in practical applications, since in backbone networks the grooming factor is usually greater than the network size. Finally, we improve this approximation ratio under some extra assumptions about the request graph. |
| Abstract: | A general instance of a \sc Degree-Constrained Subgraph problem consists of an edge-weighted or vertex-weighted graph $G$ and the objective is to find an optimal weighted subgraph, subject to certain degree constraints on the vertices of the subgraph. This class of combinatorial problems has been extensively studied due to its numerous applications in network design. If the input graph is bipartite, these problems are equivalent to classical transportation and assignment problems in operations research. This paper considers three natural \sc Degree-Constrained Subgraph problems and studies their behavior in terms of approximation algorithms. These problems take as input an undirected graph $G=(V,E)$, with $|V|=n$ and $|E|=m$. Our results, together with the definition of the three problems, are listed below. The Maximum Degree-Bounded Connected Subgraph (MDBCS$_d$) problem takes as input a weight function $\omega : E \rightarrow \mathbb R^+$ and an integer $d \geq 2$, and asks for a subset $E' \subseteq E$ such that the subgraph $G'=(V,E')$ is connected, has maximum degree at most $d$, and $\sum_e\in E' \omega(e)$ is maximized. This problem is one of the classical NP-hard problems listed by Garey and Johnson in (Computers and Intractability, W.H. Freeman, 1979), but there were no results in the literature except for $d=2$. We prove that MDBCS$_d$ is not in Apx for any $d\geq 2$ (this was known only for $d=2$) and we provide a $(\min m/ \log n,\ nd/(2 \log n))$-approximation algorithm for unweighted graphs, and a $(\min n/2,\ m/d)$-approximation algorithm for weighted graphs. We also prove that when $G$ accepts a low-degree spanning tree, in terms of $d$, then MDBCS$_d$ can be approximated within a small constant factor in unweighted graphs. The \sc Minimum Subgraph of Minimum Degree$_\geq d$ (MSMD$_d$) problem consists in finding a smallest subgraph of $G$ (in terms of number of vertices) with minimum degree at least $d$. We prove that MSMD$_d$ is not in Apx for any $d\geq 3$ and we provide an $\mathcal O(n/\log n)$-approximation algorithm for the classes of graphs excluding a fixed graph as a minor, using dynamic programming techniques and a known structural result on graph minors. In particular, this approximation algorithm applies to planar graphs and graphs of bounded genus. The \sc Dual Degree-Dense $k$-Subgraph (DDD$k$S) problem consists in finding a subgraph $H$ of $G$ such that $|V(H)| \leq k$ and $\delta_H$ is maximized, where $\delta_H$ is the minimum degree in $H$. We present a deterministic $\mathcal O(n^\delta)$-approximation algorithm in general graphs, for some universal constant $\delta < 1/3$. |
| Abstract: | In this paper we study a combinatorial optimization problem issued from on-board networks in satellites. In this kind of networks the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four links available. The paths connecting inputs to outputs should be link-disjoint. More formally, we call {it $\plk-$network } an undirected graph with $p+\lambda$ inputs, $p+k$ outputs and internal vertices of degree four. A $\plk-$network is \emph{valid} if it is tolerant to a restricted number of faults in the network, i.e. if for any choice of at most $k$ faulty inputs and $\lambda$ faulty outputs, there exist $p$ edge-disjoint paths from the remaining inputs to the remaining outputs. In the special case $\lambda=0$, a $\plk-$network is already known as a \emph{selector}. Our optimization problem consists of determining $N\plk$, the minimum number of nodes in a valid $\plk-$network. For this, we present validity certificates and a gluing lemma from which derive lower bounds for $N\plk$. We also provide constructions, and hence upper bounds, based on expanders. The problem is very sensitive to the order of $\lambda$ and $k$. For instance, when $\lambda$ and $k$ are small compared to $p$, the question reduces to avoid certain forbidden local configurations. For larger values of $\lambda$ and $k$, the problem is to find graphs with a good expansion property for small sets. This leads us to introduce a new parameter called \emph{$\alpha$-robustness}. We use $\alpha$-robustness to generalize our constructions to higher order values of $k$ and $\lambda$. In many cases, we provide asymptotically tight bounds for $N\plk$. |
| Abstract: | This article investigates the problem of designing virtual dipaths (VPs) in a directed ATM model, in which the flow of information in the two directions of a link are not identical. On top of a given physical network we construct directed VPs. Routing in the physical network is done using these VPs. Given the capacity of each physical link (the maximum number of VPs that can pass through the link) the problem consists in defining a set of VPs to minimize the diameter of the virtual network formed by these VPs (the maximum number of VPs traversed by any single message). For the most popular types of simple networks, namely the path, the cycle, the grid, the tori, the complete k-ary tree, and the general tree, we present optimal or near optimal lower and upper bounds on the virtual diameter as a function of the capacity. |
| Abstract: | In this paper, we address the problem of gathering information in a specific node (or \emph{sink}) of a radio network, where interference constraints are present. We take into account the fact that, when a node transmits, it produces interference in an area bigger than the area in which its message can actually be received. The network is modeled by a graph; a node is able to transmit one unit of information to the set of vertices at distance at most $\dt$ in the graph, but when doing so it generates interference that does not allow nodes at distance up to $\di$ ($\di \ge \dt$) to listen to other transmissions. Time is synchronous and divided into time-steps in each of which a round (set of non-interfering radio transmissions) is performed. We give general lower bounds on the number of rounds required to gather into a sink of a general graph, and present an algorithm working on any graph, with an approximation factor of 4. We also show that the problem of finding an optimal strategy for gathering is \textsc{NP-hard}, for any values of $\di$ and $\dt$. If $\di>\dt$, we show that the problem remains hard when restricted to the uniform case where each vertex in the network has exactly one piece of information to communicate to the sink. |
| Abstract: | We define and study an optimization problem that is motivated by bandwidth allocation in radio networks. Because radio transmissions are subject to interference constraints in radio networks, physical space is a common resource that the nodes have to share in such a way, that concurrent transmissions do not interfere. The bandwidth allocation problem we study under these constraints is the following. Given bandwidth (traffic) demands between the nodes of the network, the objective is to schedule the radio transmissions in such a way that the traffic demands are satisfied. The problem is similar to a multicommodity flow problem, where the capacity constraints are replaced by the more complex notion of non-interfering transmissions. We provide a formal specification of the problem that we call round weighting. By modeling non-interfering radio transmissions as independent sets, we relate the complexity of round weighting to the complexity of various independent set problems (e.g. maximum weight independent set, vertex coloring, fractional coloring). From this relation, we deduce that in general, round weighting is hard to approximate within n to the power mu (n being the size of the radio network, and mu a positive number). We also provide polynomial (exact or approximation) algorithms e.g. in the following two cases: (a) when the interference constraints are specific (for instance for a network whose vertices belong to the Euclidean space), or (b) when the traffic demands are directed towards a unique node in the network (also called gathering, analogous to single commodity flow). |