Paper Info
Title
On Finding Maximum Disjoint Paths With Different Colors: Computational Complexity And Practical Lp-Based Algorithms
Abstract
With the rapid development of wireless networks, the burden on data transmission is becoming much higher, so are the requirements for bandwidth and load balancing. To cope with these changing requirements, we investigate a novel problem of finding maximum disjoint paths with different colors (MDPDC). In MDPDC, transmission frequencies in a network are modeled as different colors on network nodes. The aim is to find a maximum number of color-constrained node-disjoint paths where nodes must share the same color within any disjoint path, and differ in color among different disjoint paths. For this proposed problem, we first prove MDPDC is MP-complete in both directed and undirected graphs. Then we provide two practical linear programming based solutions with theoretical justifications of their correctness and time complexity. Extensive computer experiments are also carried out with several compared baseline methods to demonstrate the effectiveness of proposed algorithms both in running time and solution quality. (C) 2021 Elsevier B.V. All rights reserved.
Year
DOI
Venue
2021
10.1016/j.tcs.2021.08.009
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Wireless networks, Maximum disjoint paths with different colors, NP-completeness, Linear programming
Journal
886
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
4
Name
Order
Citations
PageRank
Yunyun Deng121.02
Longkun Guo26814.71
Kewen Liao35111.16
Yi Chen45420.72