ABSTRACT We investigate a cops and robber game on directed graphs, where the robber moves along the arcs of the graph, whereas the cops can select any position at each time step. Our main focus is on the cop number: the minimum number of cops required to guarantee the capture of the robber. We prove that deciding whether the cop number of a digraph is equal to 1 is NP‐hard, whereas this is decidable in polynomial time for tournaments. Furthermore, we show that computing the cop number for general digraphs is fixed parameter tractable when parameterized by a generalization of vertex cover. However, for tournaments, tractability is achieved with respect to the minimum size of a feedback vertex set. Among our findings, we prove that the cop number of a digraph is equal to that of its reverse digraph, and we draw connections to the matrix mortality problem.

Abstract In a previous work, the authors showed that the maximum number of infinitely long synchronous directed walks that never meet is equal to the dimension of the no‐meet matroid, namely the largest order of a collection of vertex‐disjoint cycles. Given , we want to compute the meeting time of walks: the first time step such that, given any set of walks, at least two of them must meet no later than . We precisely prove that the meeting time is at most , where is the number of vertices. A connection is established with a cops and robber game on directed graphs with helicopter cops and an invisible slow robber. The meeting time of walks equals the capture time in this game, when at most capture attempts are allowed. While this capture time can be computed in polynomial time, we show that it is NP‐hard to compute the minimum number of cops needed to catch the robber. More insights are also given on the number and its relation to pathwidth and other graph parameters. Finally we analyze these game measures on digraph tensor products.

We consider robust network design problems where an uncertain traffic vector belonging to a polytope has to be dynamically routed to minimize either the network congestion or some linear reservation cost. We focus on the variant in which the underlying graph is directed. We prove that an O(√k) = O(n)-approximation can be obtained by solving the problem under static routing, where k is the number of commodities and n is the number of nodes. This improves previous results of Hajiaghayi et al. [SODA'2005] and matches the Ω(n) lower bound of Ene et al. [STOC'2016] and the Ω(√k) lower bound of Azar et al. [STOC'2003]. Finally, we introduce a slightly more general problem version where some flow restrictions can be added. We show that it cannot be approximated within a ratio of k^{c/(log log k)} (resp. n^{c/(log log n)}) for some constant c. Making use of a weaker complexity assumption, we prove that there is no approximation within a factor of 2^{log^{1- ε} k} (resp. 2^{log^{1- ε} n}) for any ε > 0.

Abstract Taking into account the dynamic nature of traffic in telecommunication networks, the robust network design problem is to fix the edge capacities so that all demand vectors belonging to a polytope can be routed. While a common heuristic for this co‐NP‐hard problem is to compute, in polynomial time, an optimal static routing, affine routing can be used to obtain better solutions. It consists in restricting the routing to affinely depend on the demands. We show that a node‐arc formulation is less conservative than an arc‐path formulation. We also provide a cycle‐based formulation that is equivalent to the node‐arc formulation. To further reduce the solution's cost, several new formulations are obtained by relaxing flow conservation constraints and aggregating demands. As might be expected, aggregation allows us to reduce the size of formulations. A more striking result is that aggregation reduces the solution's cost.

The analysis of the techno-economic interactions among the mobile operators and tenants (slices) in the context of 5G network slicing has lately received growing interest by the research community. In particular the problems of admission control, resource allocation/scheduling and pricing for network slicing are not trivial as they affect the profits of the involved stakeholders such as the operator (slice provider) and the network slice owners (tenants or service providers) and therefore the viability of the slice market. Since such problems are entwined, we propose here a novel optimization framework that jointly addresses admission control, resource allocation and pricing. In the proposed framework, the operator owns a fixed amount of resources whereas each slice is characterized by a stochastic demand and utility function reflecting its Quality of Service (QoS) requirements. We have considered two types of slices, one with low traffic profile and deterministic QoS, representing Ultra Reliable Low Latency Communications (URLLC), and one with higher traffic profile and statistical QoS, representing enhanced Mobile BroadBand (eMBB). We devise several models based on whether we allow statistical multiplexing and whether we make use of different prices for different types of slices. We also evaluate the impact of the description of traffic in an aggregate way compared to a detailed one. The outcomes of all variants are analyzed through some numerical experiments which enable us to assess the main flavors of each model.

International audience

Due to high mobility situations that are commonly envisaged for the next Fifth Generation (5G) of mobile communication systems, the wireless propagation channel becomes a time-frequency variant, where the time dispersion emerges from the multipath characteristic and the time-selectivity arises from the Doppler spread. This aspect can dramatically damage the waveforms orthogonality that is induced in the Orthogonal frequency division multiplexing (OFDM) signal. Consequently, this results in oppressive Inter-Carrier Interference (ICI) and Inter-Symbol Interference (ISI), which leads to performance degradation in OFDM systems. To efficiently overcome these drawbacks, we propose Ping-pong Optimized Pulse Shaping-OFDM (POPS-OFDM ) algorithm that maximizes the received Signal to Interference plus Noise Ratio (SINR) by optimizing systematically the OFDM waveforms at the Transmitter (TX) and Receiver (RX) sides. We derived the exact closed-form expression of the SINR of the considered multicarrier system and the optimized waveform is searched as a linear combination of several of the most localized Hermite functions. Then, we go further by testing its robustness against time synchronization errors. The results confirm the advantage behind POPS-OFDM algorithm in enhancing spectacular performance and its robustness compared to multicarrier systems using conventional waveforms. Simulations are given to support our claims.

In this article, we propose a generic decomposition scheme for the maximum concurrent flow problem. This decomposition scheme encompasses many models, including, among many others, the classical path formulation and the less studied tree formulation, where the flows of commodities sharing a same source vertex are routed on a set of trees. The pricing problem for this generic model is based on shortest‐path computations. We show that the tree‐based linear programming formulation can be solved much more quickly than the path or the aggregated arc‐flow formulation. Some other decomposition schemes can lead to even faster resolution times. Finally, an efficient strongly polynomial‐time combinatorial algorithm is proposed for the single‐source case. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 56–67. 2015

Cloud computing is very useful for improving distributed applications performance. However, it is difficult to manage risks related to trust when collaborating with unknown and potentially malicious peers. Besides, trust evaluation is the target of dishonest behaviors trying to disturb the control

Abstract This article focuses on the problem of computing a minimum‐weight subgraph with unicyclic connected components. Although this problem is generally easy, it becomes difficult when a girth constraint is added. A polyhedral study is proposed. Many facets and valid inequalities are derived. Some of them can be exactly separated in polynomial time. Hence, the problem is solved by a cutting‐plane algorithm based on these inequalities and using a compact formulation derived from the transversality of the bicircular matroid. Numerical results are also presented. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013

Inter-vehicle communication is considered as a major problem to vehicular environment. Here, an analytical framework is developed to investigate the reliability of end-to-end information relay process along a platoon of vehicles. The reliability of inter-vehicle communication is measured by the probability of success for information to travel to a known destination and by the required number of hops. In the models, recursive formulations are derived for the two previous criteria. Lower and upper bounds for our models are provided and computed by dynamic programming techniques. Simulation results match very well the mathematical expressions and show that the gap between lower and upper bounds is very small.

A beamforming-based broadcast technique is proposed here for VANETs. It is based on two key information: the direction to the destination and the beamforming angle θ. Simulations demonstrate the efficiency of our proposal in terms of probability of transmission success, ratio of implicated nodes and bandwidth gain. An analytical model is derived to calculate the forwarding transmission area. Simulation results match very well the mathematical expressions and show that the analytical model is precise.

Abstract Given G = (V,E) an undirected graph and two specified nonadjacent nodes a and b of V, a cut separator is a subset F =δ (C) ⊆ E such that a,b∈V / C and a and b belong to different connected components of the graph induced by V / C. Given a non‐negative cost vector \documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath, amssymb} \pagestyle{empty} \begin{document} \begin{align*}c\in\mathbb{R}^{|E|}_{+}\end{align*} \end{document} , the cut separator problem is to find a cut separator of minimum cost. This new problem can be seen as a generalization of the vertex separator problem. In this article, we give a polynomial time algorithm for this problem. We also present six equivalent linear programming formulations, and we show their tightness. Using these results we obtain an explicit short polyhedral description of the dominant of the cut separator polytope. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

This paper focuses on the design of minimum-cost networks satisfying two technical constraints. First, the connected components should be unicyclic. Second, some given special nodes must belong to cycles. This problem is a generalization of two known problems: the perfect binary 2-matching problem and the problem of computing a minimum-weight basis of the bicircular matroid. It turns out that the problem is polynomially solvable. An exact extended linear formulation is provided. We also present a partial description of the convex hull of the incidence vectors of these Steiner networks. Polynomial-time separation algorithms are described. One of them is a generalization of the Padberg–Rao algorithm to separate blossom inequalities.

In the paper we deal with the problem of optimal partitioning of a traffic demand polytope using a hyperplane. In the considered model all possible demand matrices belong to a polytope. The polytope can be divided into parts, and different routing schemes can be considered while dealing with traffic matrices from different parts of the polytope. The model can be applied to all networks that support unrestricted routing of bifurcated flows, e.g., MPLS networks or optical networks. In the paper we present an algorithm that solves one of the most practical versions of the considered problem, i.e., reservation vectors on both sides of the hyperplane have to be the same. Moreover, we present another (faster) algorithm that solves a more restricted version of the problem. Finally, we present numerical results proving the applicability of the introduced algorithms.

Abstract The maximum cut problem is a classical combinatorial optimization problem that is known to be NP‐hard in general. In the present article, we provide some new lower and upper bounds that are based on the eigenvalues of the weight matrix with modified diagonal entries. Namely, we show that some upper bounds presented here are generally better than the SDP bound introduced by Goemans and Williamson, JACM 42 (1995), 1115–1145. We also discuss the complexity of computing these bounds and provide some preliminary computational results. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract Most of integer, convex, and large‐scale linear problems are solved using cutting plane and column generation algorithms. Therefore, to handle large‐size problems and to reduce the computing times, it may be very useful to accelerate cutting plane algorithms. We show in this article that we can achieve this goal by choosing good separation points. Focus is given on problems for which we have an exact separation oracle. An in–out algorithm is proposed, and the convergence is proved under some general assumptions. Computational experiments related to three classes of problems, survivable network design, multicommodity flow problems, and random linear programs, clearly point out the savings of time allowed by the simple in–out approach proposed in this article. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 3–17 2007

Abstract This report surveys the papers presented at the International Network Optimization Conference (INOC2005), held in Lisbon, Portugal, March 2005. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 1–6 2006

Abstract This report highlights some recent contributions to network optimization based on papers presented at the first International Network Optimization Conference (INOC'2003) held in Evry‐Paris, France. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 27–30 2004

In most domains of the Internet network, the traffic demands are routed on a single-path defined as the shortest one according to a set of administrative weights. Most of the time, the values set by the administrator (or the default ones) are such that there are many paths of the same length between the extremities of some demands. However, if the shortest paths are not unique, it might become difficult for an Internet domain administrator to predict and control the traffic flows in the network. Moreover, the sequence order of packets can be changed when many paths are used leading to some end-to-end delays. It is hence an important issue to ensure that each shortest path is unique according to a given set of administrative weights. We show that it is possible to determine a set of small integer weights (smaller than 6 times the radius of the network) such that all links are used and every demand is routed on a unique shortest path. Above and beyond this uniqueness requirement, network administrators wishing to exploit the available resources would like to control the whole routing pattern. The problem they face consists of determining a set of weights enforcing a given routing policy. We formulate this problem using linear programs, and we show how integer weights can be computed by heuristics with guaranteed worst-case performances. Some conditions on the given routing, necessary for the existence of a solution, are derived. Both necessary and sufficient conditions are also provided, together with some other useful properties, in the case of particular graphs such as cycles and cacti.

Some problems related to constrained length connectivity are addressed in this paper. Let Sl(x, y) be the minimum number of vertices that should be removed to destroy all the paths of length at most l between two vertices x and y. Let Il(x, y) be the maximum number of such node-disjoint paths. We first focus on f(l, d), defined as the supremum of (Sl(x, y))/(Il(x, y)) taken over all graphs and all pairs of x, y separated by a distance d. One of the results shown in this paper states that this supremum is exactly equal to l + 1 − d when d ≥ ⌈⅔l + 1)⌉ and is at least constant when 2 ≤ d ≤ 2 + ⌊(l + 1)/3⌋. Some classes of two connected graphs satisfying path-length constraints are defined. Most of them describe survivable telecommunication networks. Relationships between flows and constrained length connectivity are addressed. We also study the minimum edge numbers of these two connected graphs. Some of their topological properties are presented. © 2000 John Wiley & Sons, Inc.