Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks

Rafael F. Santos, Alessandro Andrioni, Andre C. Drummond and Eduardo C. Xavier ()
Additional contact information
Rafael F. Santos: University of Campinas, UNICAMP
Alessandro Andrioni: University of Campinas, UNICAMP
Andre C. Drummond: University of Brasilia
Eduardo C. Xavier: University of Campinas, UNICAMP

Journal of Combinatorial Optimization, 2017, vol. 33, issue 2, No 22, 742-778

Abstract: Abstract In this paper we study a problem of finding coloured paths of minimum weight in graphs. This problem has applications in WDM optical networks when high bandwidths are required to send data between a pair of nodes in the graph. Let $$G=(V,E)$$ G = ( V , E ) be a (directed) graph with a set of nodes V and a set of edges E in which each edge has an associated positive weight w(i, j), and let $$C = \{1, 2, \ldots , x\}$$ C = { 1 , 2 , … , x } be a set of x colours, $$x \in {\mathbb {N}}$$ x ∈ N . The function $$c : E \mapsto 2^C$$ c : E ↦ 2 C maps each edge of the graph G to a subset of colours. We say that edge e contains colours $$c(e) \subseteq C$$ c ( e ) ⊆ C . Given a positive integer $$k > 1$$ k > 1 , a k-multicolour path is a path in G such that there exists a set of k colours $$K = \{c_1, \ldots , c_k\} \subseteq C$$ K = { c 1 , … , c k } ⊆ C , with $$K \subseteq c(i,j)$$ K ⊆ c ( i , j ) for each edge (i, j) in the path. The problem of finding one or more k-multicolour paths in a graph has applications in optical network and social network analysis. In the former case, the available wavelengths in the optical fibres are represented by colours in the edges and the objective is to connect two nodes through a path offering a minimum required bandwidth. For the latter case, the colours represent relations between elements and paths help identify structural properties in such networks. In this work we investigate the complexity of the multicolour path establishment problem. We show it is NP-hard and hard to approximate. Additionally, we develop Branch and Bound algorithms, ILPs, and heuristics for the problem. We then perform an experimental analysis of the developed algorithms to compare their performances.

Keywords: Minimum paths in coloured graphs; NP-hardness; Heuristics; WDM networks (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0003-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:2:d:10.1007_s10878-016-0003-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0003-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().