II. REPORT 2010

Description of the results for 2010

One of the main goal of Equipe Associée EWIN is to favour students exchanges and it has been attained. Indeed, most of the missions in the frame of EWIN have been done by Master or PhD students. In addition, Ronan Soares, a Master student in Fortaleza obtained a grant to do a cosupervised PhD. He starts in November 2010.

Regarding the scientific objectives, we followed the programme as planned in the proposal 2010 .

• Channel assignment and graph colouring We studied a problem of frequencies assignment for diffusion from a satellite towards land receivers. We also studied on-line colouring in order to better understand dynamic assignments.
  
  
  • Reception from satellite and improper colouring
    We studied the following problem posed by Alcatel Space Technologies. A satellite sends informations to receivers on earth, each of which is listening several frequencies, one for each signal it needs to receive. Technically it is impossible to focus a signal sent by the satellite exactly on the destination receiver. So part of the signal is spread in an area around it, creating noise for the other receivers displayed in this area and listening the same frequency. Each receiver is able to distinguish the signal directed to it from the extraneous noises it picks up if the sum of the noises does not become too large, i.e. does not exceed a certain threshold T. The problem is to assign frequencies to the signals in such a way that each receiver gets its dedicated signals properly, while minimizing the total number of frequencies used. This problem models in terms of weighted imprper colouring of the conflict graph. The vertices of this graph are the receivers and two vertices are linked by an edge if these receivers interfere. A k-improper colouring is a colouring of the vertices such that every vertex has at most $k$ neighbours of its colour. In [BHHL10], we built approximate algorithms giving k-improper colourings of weighted graphs of certain classes. In particular, we gave results of hexagonal graphs which are real-life conflicts graphs that are obtained when the reception area is divided into hexagonal cells.
  • On-line colouring Lots of channel assignments are done on-line. Hence in order better understand such a problematic, we studied greedy colouring [AHL10,CGH+10] which is the easiest and the most widely used on-line colouring procedure. We also studied b-colouring [HLS10] which measures to which extend some on-line colouring improvement algorithms may perform.
  
  
• Configuration and routing in wireless networks
  Technological breakthroughs have transformed the telecommunications industry aiming at providing capacity and efficiency to support the increasing demand for wireless broadband services. With the advances in access technologies, the capacity bottleneck of cellular networks is gradually moving from the radio interface towards the backhaul -- the portion of the network infrastructure that provides interconnectivity between the access and core networks. The ability for microwave to be rapidly and cost-effectively deployed is being a crucial point for successfully tackling the backhaul bottleneck problem. Nevertheless, backhaul solutions available with this technology have received little attention from the scientific community. As microwave backhaul becomes larger and more complex, several interesting problems from network optimization arise in this developing area. In addition, due to fundamental differences between wireless networks and classical wired networks, a variety of questions remain to be adequately addressed, and some additional considerations inherent to wireless communications must be taken into account for better responding some of them. Therefore, more refined approaches for dealing with network optimization in wireless microwave backhaul need to be conceived. This is the main issue that we addressed [Nep10], which was partially developed within the scope of the joint project RAISOM, among INRIA Sophia Antipolis, SME 3Roam, and SME Avisto. We investigated network optimization problems related to the design and configuration of wireless microwave backhaul. We are concerned with a general class of problems expressed in terms of minimum cost multicommodity flows with discrete cost functions on the nodes and/or links of the network. Discrete cost multicommodity flow problems are among the most important and challenging problems in network optimization. Generally, they are computationally very difficult and, in practice, can only be solved approximately. We introduce mathematical models for some of these problems and present solution approaches essentially based on general mixed integer programming, chance-constrained programming, relaxation techniques, cutting plane methods, as well as hybrid metaheuristics.



• Graphs decompositions and routing reconfiguration
  

  Both partner teams work on graphs decompositions like tree-decompositions defined by Robertson and Seymour in their Graph Minors theory. Beside their theoretical interest, these decompositions have many algorithmic applications. In particular, many NP-complete problems can be solved in polynomial time when restricted to classes of graphs with small treewidth, i.e., admitting "good" decompositions. Moreover, these decompositions have an interesting algorithmic interpretation in terms of graph searching game, a.k.a. pursuit-evasion games : their widths (treewidth, pathwidth...) correspond to the smallest number of searchers required to capture a fugitive in a graph in the different variants of graph searching games. Recently, we [Coudert et al, Rerouting requests in WDM networks] proposed to model a routing reconfiguration problem in MPLS or WDM networks as a variant of graph searching in digraphs. The initial problem is to schedule the interruptions and reroutings of a set of requests in a network in order to minimize the number of simultaneously interrupted during the reconfiguration process. The problem is NP-complete in general, hence in previous work, we proposed heuristics and studied particular digraph classes. For networks operators, the real cost of a routing reconfiguration also depends on other parameters as the total number of the requests that are interrupted during the process and the duration of such interruptions. We established [CCM+10a, CCM+10b] tradeoffs between some of these parameters. Moreover, Ronan Soares did a master thesis [Soa10] supervised by Claudia Linhares Sales, with a three months internship in the MASCOTTE team, on graph searching problems applied to the interruptions duration parameter. We also worked on some other problems related to graph searching games [CCNV10].





Articles in international journals

[AHL10] M. Asté, F. Havet and C. Linhares Sales. Grundy number and products of graphs. Discrete Mathematics, 310(9):1482--1490, 2010. PDF

[BHHL10] J.-C. Bermond, F. Havet, F. Huc, and C. Linhares Sales. Improper colouring of weighted grid and hexagonal graphs. Discrete Mathematics, Algorithms and Applications, to appear, 2010. PDF

[CNR10] D. Coudert, N. Nepomuceno, and H. Rivano. Power-Efficient Radio Configuration in Fixed Broadband Wireless Networks. Computer Communications, Special Section on Hot Topics in Mesh Networking, 33(8):898-906, 2010. PDF



Communications in conferences

[ASL10] J. Araujo, C. Linhares Sales, and I. Sau. Weighted Coloring on $P_4$-sparse Graphs. In 11es Journées Doctorales en Informatique et Réseaux (JDIR 2010), Sophia Antipolis, France, pages 33--38, March 2010. PDF

[CCNV10] J. Chalopin, V. Chepoi, N. Nisse, and Y. Vaxes. Cop and robber games when the robber can hide and ride. In 8th French Combinatorial Conference, Orsay, June 2010.

[CCM+10a] N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, and N. Nisse. Tradeoffs in process strategy games with application in the WDM reconfiguration problem. In P. Boldi and L. Gargano, editors, Fifth International conference on Fun with Algorithms (FUN 2010), volume 6099 of Lecture Notes in Computer Science, Ischia Island, Italy, pages 121-132, June 2010. Springer. PDF

[CCM+10b] N. Cohen, D. Coudert, D. Mazauric, N. Nepomuceno, and N. Nisse. Tradeoffs in routing reconfiguration problems. In 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), Belle Dune France, pages 4p, 2010. PDF

[Cou10] D. Coudert Graph searching games for the WDM reconfiguration problem. In 24th European Conference on Operational Research (EURO), Lisbon, Portugal, pages 1p, July 2010. Invited talk.

[Nis10] N. Nisse. Graph Searching and Graph Decompositions. In 24th European Conference on Operational Research (EURO), Lisbon, Portugal, pages 1p, July 2010.

PhD thesis

[Nep10] N. Nepomuceno.Network optimization for wireless microwave backhaul. PhD thesis Université de Nice-Sophia Antipolis, 2010

Master thesis

[Soa10] R. Soares Procura em grafos. Master thesis, Federal University of Fortaleza, 2010.



Internal reports

[CGH+10] V. Campos, A. Gyárfás, F. Havet, C. Linhares-Sales, and F. Maffray. New bounds on the Grundy number of products of graphs. Research Report 7243, INRIA, April 2010. PDF

[HLS10] F. Havet, C. Linhares Sales, and L. Sampaio. b-coloring of tight graphs. Research Report 7241, INRIA, March 2010. PDF