The widest k -set of disjoint paths problem Ribeiro, Marco Antônio; Carvalho, Iago Augusto; Pereira, Armando Honório
R.A.I.R.O. Recherche opérationnelle,
01/2023, Volume:
57, Issue:
1
Journal Article
Peer reviewed
Open access
Finding disjoint and widest paths are key problems in telecommunication networks. In this paper, we study the Widest
k
-set of Disjoint Paths Problem (WKDPP), an
NP
-Hard optimization problem that ...considers both aspects. Given a digraph
G
= (
N
,
A
), WKDPP consists of computing
k
arc-disjoint paths between two nodes such that the sum of its minimum capacity arcs is maximized. We present three mathematical formulations for WKDPP, a symmetry-breaking inequality set, and propose two heuristic algorithms. Computational experiments compare the proposed heuristics with another from the literature to show the effectiveness of the proposed methods.
Two Algorithms for the k-Widest Path Problem Gomes, Teresa; Martins, Lúcia; Craveirinha, José M. F. ...
Journal of network and systems management,
07/2023, Volume:
31, Issue:
3
Journal Article
Peer reviewed
In communication networks where services require a certain amount of bandwidth for setting up a connection, an important problem (to be referred to as the
k
-widest path problem) is to enumerate ...paths in non-increasing order of the bandwidth availability of the paths. For this problem, a path follows a non-additive, concave cost property. Notably, this problem parallels the
k
-shortest path problem for which the path cost is additive. We present two exact algorithms for solving this problem, denoted by kWP-1 and kWP-2, inspired by the loopless version of MPS (Martins–Pascoal–Santos) algorithm and Yen’s algorithm for the
k
-shortest path algorithm, respectively. Our numerical study shows that kWP-2 is more effective than kWP-1 for the
k
-widest path problem, in contrast with the relatively better performance of MPS over Yen’s algorithm regarding the enumeration of
k
-shortest paths.
Short and Wide Network Paths Marla, Lavanya; Varshney, Lav R.; Shah, Devavrat ...
IEEE transactions on network science and engineering,
03/2022, Volume:
9, Issue:
2
Journal Article
Peer reviewed
Open access
Network flow is a powerful mathematicalframework to systematically explore the relationship between structure and function in biological, social, and technological networks. We introduce a new ...pipelining model of flow through networks where commodities must be transported over single paths rather than split over several paths and recombined. We show this notion of pipelined network flow is optimized using network paths that are both short and wide, and develop efficient algorithms to compute such paths for given pairs of nodes and for all-pairs. Short and wide paths are characterized for many real-world networks. Using this framework, we further develop novel information-theoretic lower bounds on computation speed in nervous systems due to limitations from anatomical connectivity and physical noise. This provides predictions on the structural organization and behavior of the nematode Caenorhabditis elegans .
We consider the problem of precomputing constrained widest paths and multicast trees in a communication network. Precomputing and storing of the relevant information minimizes the computational ...overhead required to determine an optimal path when a new connection request arrives. We evaluate algorithms that precompute paths with maximal bandwidth (widest paths), which in addition satisfy given end-to-end delay constraints. We analyze and compare both the worst case and average case performance of the algorithms. We also show how the precomputed paths can be used to provide computationally efficient solutions to the constrained widest multicast tree problem. In this problem, a multicast tree with maximal bandwidth (widest multicast tree) is sought, which in addition satisfies given end-to-end delay constraints for each path on the tree from the source to a multicast destination.
In collaborative applications, participants agree on certain level of secure communication based on communication policy specifications. Given secure communication policy specifications of various ...group members at design time, the minimum set of resources for a pair, called resolved policy level agreement (RPLA) is translated into appropriate security service implementations, for the pair-wise communication to take place. We propose a novel idea that the members may extend pair-wise communication quality through other trusted nodes whose communication resources offer more security. We propose a heuristic algorithm which finds the best quality of protection (QoP), a measure of the resistance to an attack, path through coalition of trusted nodes. The results from our experiments indicate a significant improvement in QoP in the range of 13% to 48% over pair-wise communications.
PDF
