Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s11424-017-6138-0 | J. Systems Science & Complexity |
Keywords | Field | DocType |
Edge-coloured chain graph, minimal paths, multimodal networks, Pareto set cardinality, upper bounds | Block graph,Discrete mathematics,Combinatorics,Mathematical optimization,Indifference graph,Line graph,Distance-hereditary graph,Independent set,Cograph,Pathwidth,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
31 | 2 | 1009-6124 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Ensor | 1 | 10 | 4.23 |
| Felipe Lillo | 2 | 2 | 1.79 |