Constrained Connectivity in Bounded XWidth MultiInterface Networks As technology advances and the spreading of wireless devices grows, the establishment of interconnection networks is becoming crucial. Main activities that involve most of the people concern retrieving and sharing information from everywhere. In heterogeneous networks, devices can communicate by means of multiple interfaces. The choice of the most suitable interfaces to activate (switchon) at each device results in the establishment of different connections. A connection is established when at its endpoints the devices activate at least one common interface. Each interface is assumed to consume a specific percentage of energy for its activation. This is referred to as the cost of an interface. Due to energy consumption issues, and the fact that most of the devices are battery powered, special effort must be devoted to suitable solutions that prolong the network lifetime. In this paper, we consider the socalled pCoverage problem where each device can activate at most p of its available interfaces in order to establish all the desired connections of a given network of devices. As the problem has been shown to be    NP   hard even for     p  2     and unitary costs of the interfaces, algorithmic design activities have focused in particular topologies where the problem is optimally solvable. Following this trend, we first show that the problem is polynomially solvable for graphs (modeling the underlying network) of bounded treewidth by means of the Courcellexe2x80x99s theorem. Then, we provide two optimal polynomial time algorithms to solve the problem in two subclasses of graphs with bounded treewidth that are graphs of bounded pathwidth and graphs of bounded carvingwidth. The two solutions are obtained by means of dynamic programming techniques.

Small Cuts and Connectivity Certificates: A Fault Tolerant Approach We revisit classical connectivity problems in the CONGEST model of distributed computing. By using techniques from fault tolerant network design, we show improved constructions, some of which are even local (i.e., with widetildeO(1) rounds) for problems that are closely related to hard global problems (i.e., with a lower bound of Omega(Diamsqrtn) rounds).  :52,main results are:  :56,For Ddiameter unweighted graphs with constant edge connectivity, we show an exact distributed deterministic computation of the minimum cut in poly(D) rounds. This resolves one the open problems recently raised in Daga, Henzinger, Nanongkai and Saranurak, STOCu002719.  :56,For Ddiameter unweighted :94,graphs, we present a deterministic algorithm that computes of all edge connectivities up to constant in poly(D)cdot 2O(sqrtlog nloglog n) rounds.  :119,Computation of sparse lambda connectivity certificates in widetildeO(lambda) rounds. Previous constructions where known only for lambda leq 3 and required O(D) rounds. This resolves the problem raised by Dori PODCu002718.