On the shortest path problems with edge constraints

Ferone, Daniele, Festa, Paola, Fugaro, Serena and Pastore, Tommaso (2020) On the shortest path problems with edge constraints. In: 2020 22nd International Conference on Transparent Optical Networks, ICTON 2020. International Conference on Transparent Optical Networks . The Institute of Electrical and Electronics Engineers (IEEE), ITA. ISBN 9781728184234

Full text not available from this repository.

Abstract

The goal of this work is to provide a brief classification of some Shortest Path Problem (SPP) variants that include edge constraints and that find applications in several different contexts, including optical networks, transportation and logistics. One of the most broad and notable classes of edge-constrained SPPs is given by Resource Constrained Shortest Path Problems (RCSPPs). In RCSPPs, in addition to the customary directed graph G=(V, A) and edge-distance function, a L-dimensional vector of resources R is defined. Essentially, each resource is related to relevant link attributes that need to be accounted for in the planning of the path. Accordingly, a path P∗ is optimal whenever it is minimal w.r.t. the distance function, and satisfies the restrictions enforced on the resources Other variants can involve colors assigned to the nodes and/or the edges of the graph and/or reload costs. These kinds of problems have relevant applications in network reliability. Particularly interesting is the so-called k-Color SPP, where a color is assigned to each edge and the minimum path from a given source node s to a target node t must not cross more than k differently colored edges. As for the use of reload cost, a reload cost r(b, c) is assigned to each pair of colors (b, c) and represents the amount to be paid if in a path P an arc of color c is traversed after an arc of color b.

Item Type:	Book Section
Additional Information:	Publisher Copyright: © 2020 IEEE.
Uncontrolled Keywords:	colored paths,constrained shortest path problem,network flow problems,computer networks and communications,electrical and electronic engineering,electronic, optical and magnetic materials ,/dk/atira/pure/subjectarea/asjc/1700/1705
Related URLs:	https://www.scopus.com/pages/publication...
Depositing User:	LivePure Connector
Date Deposited:	12 May 2026 09:56
Last Modified:	12 May 2026 09:56
URI:	https://ueaeprints.uea.ac.uk/id/eprint/102957
DOI:	10.1109/ICTON51198.2020.9203378

Actions (login required)

View Item