Abstract | ||
---|---|---|
A weighted coloured-edge 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 coloured-edge graph. Additionally, a bound is presented on the expected number of minimal paths in weighted bicoloured-edge graphs. |
Year | Venue | Keywords |
---|---|---|
2011 | CoRR | graph theory |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Line graph,Distance-hereditary graph,Regular graph,Null graph,Floyd–Warshall algorithm,Butterfly graph,Voltage graph,Mathematics,Complement graph | Journal | abs/1112.3066 |
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 |