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

DOI10.1007/s10878-016-0003-2zbMath1390.90552OpenAlexW2312417503MaRDI QIDQ511728

Andre C. Drummond, Alessandro Andrioni, Rafael F. Santos, Eduardo Candido Xavier

Publication date: 22 February 2017

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-016-0003-2

zbMATH Keywords

heuristicsNP-hardnessminimum paths in coloured graphsWDM networks

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items

Finding disjoint paths on edge-colored graphs: more tractability results ⋮ A temporal logic programming approach to planning

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• On the maximum disjoint paths problem on edge-colored graphs
• A note on a maximum \(k\)-subset intersection problem
• Maximum disjoint paths on edge-colored graphs: approximability and tractability
• Some extremal results on the colorful monochromatic vertex-connectivity of a graph
• On the complexity of path problems in properly colored directed graphs
• Rainbow connections of graphs: a survey
• On the strong rainbow connection of a graph
• A survey on vertex coloring problems
• Line planning, path constrained network flow and inapproximability
• Disjoint paths in a network
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Reducibility among Combinatorial Problems
• Covering Pairs in Directed Acyclic Graphs
• Benchmarking optimization software with performance profiles.