[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On the Tractability of Shortest Path Problems in Weighted Edge-Coloured Graphs

  • Published:
Journal of Systems Science and Complexity Aims and scope Submit manuscript

Abstract

A weighted edge-coloured graph is a graph for which each edge is assigned both a positive weight and a discrete colour, and can be used to model transportation and computer networks in which there are multiple transportation modes. In such a graph paths are compared by their total weight in each colour, resulting in a Pareto set of minimal paths from one vertex to another. This paper will give a tight upper bound on the cardinality of a minimal set of paths for any weighted edge-coloured graph. Additionally, a bound is presented on the expected number of minimal paths in weighted edge–bicoloured graphs. These bounds indicate that despite weighted edge-coloured graphs are theoretically intractable, amenability to computation is typically found in practice.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ensor A and Lillo F, Colored-edge graph approach for the modeling of multimodal transportation systems, Asia-Pacific Journal of Operational Research, 2016, 33(1): 16500005.

    Article  MathSciNet  MATH  Google Scholar 

  2. Clímaco J, Captivo M, and Pascoal M, On the bicriterion-minimal cost/minimal label-spanning tree problem, European Journal of Operational Research, 2010, 204(2): 199–205.

    Article  MathSciNet  MATH  Google Scholar 

  3. Xu H Y, Li K W, Kilgour D M, et al., A matrix-based approach to searching colored paths in a weighted colored multidigraph, Applied Mathematics and Computation, 2009, 215(1): 353–366.

    Article  MathSciNet  MATH  Google Scholar 

  4. Manoussakis Y, Alternating paths in edge-colored complete graphs, Discrete Applied Mathematics, 1995, 56(2–3): 297–309.

    Article  MathSciNet  MATH  Google Scholar 

  5. Bang-Jensen J and Gutin G, Alternating cycles and paths in edge-coloured multigraphs: A survey, Discrete Mathematics, 1997, 165–166: 39–60.

    Article  MathSciNet  MATH  Google Scholar 

  6. Röglin H and Vöcking B, Smoothed analysis of integer programming, Proceedings of the 11th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 2005, 276–290.

    Chapter  Google Scholar 

  7. Beier R, Röglin H, and Vöcking B, The smoothed number of pareto optimal solutions in bicriteria integer optimization, eds. by Fischetti M and Williamson D, Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2007, 53–67.

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computing and Mathematical Sciences, Auckland University of Technology, 2 - 14 Wakefield St, Auckland, 1142, New Zealand

    Andrew Ensor

  2. Department of Economics and Management, Universidad Católica del Maule, PO Box 617, Avenida San Miguel, 3605, Talca, Chile

    Felipe Lillo

Authors
  1. Andrew Ensor
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Felipe Lillo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrew Ensor.

Additional information

This research was partly supported by Católica del Maule University Through the Project MECESUP–UCM0205.

This paper was recommended for publication by Editor-in-Chief GAO Xiao-Shan.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ensor, A., Lillo, F. On the Tractability of Shortest Path Problems in Weighted Edge-Coloured Graphs. J Syst Sci Complex 31, 527–538 (2018). https://doi.org/10.1007/s11424-017-6138-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11424-017-6138-0

Keywords

Search

Navigation