Loading...
On finding maximum disjoint paths with different colors : Computational complexity and practical LP-based algorithms
Deng, Yunyun Guo, Longkun Liao, Kewen Chen, Yi
Deng, Yunyun
Guo, Longkun
Liao, Kewen
Chen, Yi
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 NP-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.
Keywords
wireless networks, maximum disjoint paths with different colors, np-completeness, linear programming
Date
2021
Type
Journal article
Journal
Theoretical Computer Science
Book
Volume
886
Issue
Page Range
157-168
Article Number
ACU Department
Peter Faber Business School
Faculty of Law and Business
Faculty of Law and Business
Collections
Relation URI
Source URL
Event URL
Open Access Status
License
All rights reserved
File Access
Controlled