We introduce and study the complexity of Path Packing. Given a graph $G$ and a list of paths, the task is to embed the paths edge-disjoint in $G$. This generalizes the well known Hamiltonian-Path problem. Since Hamiltonian Path is efficiently solvable for graphs of small treewidth, we study how this result translates to the much more general Path Packing. On the positive side, we give an FPT-algorithm on trees for the number of paths as parameter. Further, we give an XP-algorithm with the combined parameters maximal degree, number of connected components and number of nodes of degree at least three. Surprisingly the latter is an almost tight result by runtime and parameterization. We show an ETH lower bound almost matching our runtime. Moreover, if two of the three values are constant and one is unbounded the problem becomes NP-hard. Further, we study restrictions to the given list of paths. On the positive side, we present an FPT-algorithm parameterized by the sum of the lengths of the paths. Packing paths of length two is polynomial time solvable, while packing paths of length three is NP-hard. Finally, even the spacial case EPC where the paths have to cover every edge in $G$ exactly once is already NP-hard for two paths on 4-regular graphs.

Given an edge‐weighted graph G and two distinct vertices s and t of G, the next‐to‐shortest path problem asks for a path from s to t of minimum length among all paths from s to t except the shortest ones. In this article, we consider the version where G is directed and all edge weights are positive. Some properties of the requested path are derived when G is an arbitrary digraph. In addition, if G is planar, an ‐time algorithm is proposed, where n is the number of vertices of G. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(3), 205–211 2015

The usage of wireless sensor networks (WSNs) to monitor a region is an important functionality in defense and security applications. In these applications, a fundamental issue is to determine the minimum degree of coverage in the concerned region. The past researches focus on the binary disk sensing model, where sensors are assumed to be accurate in detecting targets within their sensing ranges. In this paper, we investigate the coverage problem under a more realistic model, the probabilistic sensing model, in which the probability of detection by a sensor decays with the distances. We generalize the coverage problem to the probabilistic sensing model and propose an algorithm to calculate the minimum degree of coverage. The accuracy of the proposed algorithm is verified via simulations.

Abstract In this paper, we are concerned with the problem of deploying two servers in a tree network, where each server may fail with a given probability. Once a server fails, the other server will take full responsibility for the services. Here, we assume that the servers do not fail simultaneously. In the backup 2‐center problem, we want to deploy two servers at the vertices such that the expected distance from a farthest vertex to the closest functioning server is minimum. In the backup 2‐median problem, we want to deploy two servers at the vertices such that the expected sum of distances from all vertices to the set of functioning servers is minimum. We propose an O(n)‐time algorithm for the backup 2‐center problem and an O(n log n)‐time algorithm for the backup 2‐median problem, where n is the number of vertices in the given tree network. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009