Search

Several studies demonstrate that there are critical differences between real wireless networks and simulation models. This finding has permitted to extract spatial and temporal properties for links and to provide efficient methods as biased link sampling to guarantee efficient routing structure. Other works have focused on computing metrics to improve routing, specially the reuse of the measure of entropy. From there, rises the idea of formulating a new measure of entropy that gives an overview of the spatiotemporal stability of a link. This measure will rely on spatial and temporal properties of links and fed with the efficiency of biased link sampling., Comment: 10 pages, Telecom SudParis Research Report

A path is said to be l-bounded if it contains at most l edges. We consider two types of l-bounded disjoint paths problems. In the maximum edge- or node-disjoint path problems MEDP(l) and MNDP(l), the task is to find the maximum number of edge- or node-disjoint l-bounded (s,t)-paths in a given graph G with source s and sink t, respectively. In the weighted edge- or node-disjoint path problems WEDP(l) and WNDP(l), we are also given an integer k∈ℕ and non-negative edge weights ce∈ℕ, e∈E, and seek for a minimum weight subgraph of G that contains k edge- or node-disjoint l-bounded (s,t)-paths. Both problems are of great practical relevance in the planning of fault-tolerant communication networks, for example. Even though length-bounded cut and flow problems have been studied intensively in the last decades, the $\mathcal{NP}$-hardness of some 3- and 4-bounded disjoint paths problems was still open. In this paper, we settle the complexity status of all open cases showing that WNDP(3) can be solved in polynomial time, that MEDP(4) is $\mathcal{AP\kern-1.5ptX}$-complete and approximable within a factor of 2, and that WNDP(4) and WEDP(4) are $\mathcal{AP\kern-1.5ptX}$-hard and $\mathcal{NPO}$-complete, respectively.