Mostrar el registro sencillo de la publicación
On the tractability of shortest path problems in weighted edge-coloured graphs
| dc.contributor.author | Ensor, Andrew | |
| dc.contributor.author | Lillo-Viedma, Felipe | |
| dc.date.accessioned | 2018-04-25T13:03:10Z | |
| dc.date.available | 2018-04-25T13:03:10Z | |
| dc.date.issued | 2018 | |
| dc.identifier.uri | http://repositorio.ucm.cl/handle/ucm/1724 | |
| dc.description.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. | es_CL |
| dc.language.iso | en | es_CL |
| dc.rights | Atribución-NoComercial-SinDerivadas 3.0 Chile | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | * |
| dc.source | Journal of Systems Science and Complexity, 31(2), 527–538 | es_CL |
| dc.subject | Edge-coloured chain graph | es_CL |
| dc.subject | Multimodal networks | es_CL |
| dc.subject | Pareto set cardinality | es_CL |
| dc.title | On the tractability of shortest path problems in weighted edge-coloured graphs | es_CL |
| dc.type | Article | es_CL |
| dc.ucm.facultad | Facultad de Ciencias Sociales y Económicas | es_CL |
| dc.ucm.indexacion | Scopus | es_CL |
| dc.ucm.indexacion | Isi | es_CL |
| dc.ucm.uri | sibib2.ucm.cl:2048/login?url=https://link.springer.com/article/10.1007%2Fs11424-017-6138-0 | es_CL |
| dc.ucm.doi | doi.org/10.1007/s11424-017-6138-0 | es_CL |
Ficheros en la publicación
| Ficheros | Tamaño | Formato | Ver |
|---|---|---|---|
|
No hay ficheros asociados a esta publicación. |
|||
Esta publicación aparece en la(s) siguiente(s) colección(ones)
Excepto si se señala otra cosa, la licencia de la publicación se describe como Atribución-NoComercial-SinDerivadas 3.0 Chile