On the tractability of shortest path problems in weighted edge-coloured graphs

DOI10.1007/s11424-017-6138-0zbMath1402.05121OpenAlexW2618092212MaRDI QIDQ1621167

Andrew Ensor, Felipe Lillo

Publication date: 8 November 2018

Published in: Journal of Systems Science and Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11424-017-6138-0

zbMATH Keywords

upper boundsminimal pathsedge-coloured chain graphmultimodal networksPareto set cardinality

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (1)

Colored-Edge Graph Approach for the Modeling of Multimodal Transportation Systems

Cites Work

• A matrix-based approach to searching colored paths in a weighted colored multidigraph
• Alternating cycles and paths in edge-coloured multigraphs: A survey
• Alternating paths in edge-colored complete graphs
• On the bicriterion - minimal cost/minimal label - spanning tree problem
• Colored-Edge Graph Approach for the Modeling of Multimodal Transportation Systems
• Smoothed Analysis of Integer Programming
• The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization

This page was built for publication: On the tractability of shortest path problems in weighted edge-coloured graphs