On finding maximum disjoint paths with different colors : Computational complexity and practical LP-based algorithms
Journal article
Deng, Yunyun, Guo, Longkun, Liao, Kewen and Chen, Yi. (2021). On finding maximum disjoint paths with different colors : Computational complexity and practical LP-based algorithms. Theoretical Computer Science. 886, pp. 157-168. https://doi.org/10.1016/j.tcs.2021.08.009
Authors | Deng, Yunyun, Guo, Longkun, Liao, Kewen and 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 |
Year | 2021 |
Journal | Theoretical Computer Science |
Journal citation | 886, pp. 157-168 |
Publisher | Elsevier B.V. |
ISSN | 0304-3975 |
Digital Object Identifier (DOI) | https://doi.org/10.1016/j.tcs.2021.08.009 |
Scopus EID | 2-s2.0-85113805088 |
Research or scholarly | Research |
Page range | 157-168 |
Publisher's version | License All rights reserved File Access Level Controlled |
Output status | Published |
Publication dates | |
Online | 12 Aug 2021 |
Publication process dates | |
Accepted | 08 Aug 2021 |
Deposited | 04 Jul 2022 |
https://acuresearchbank.acu.edu.au/item/8xz8q/on-finding-maximum-disjoint-paths-with-different-colors-computational-complexity-and-practical-lp-based-algorithms
Restricted files
Publisher's version
83
total views0
total downloads0
views this month0
downloads this month