|
|||||
|
|
Simple paths with exact and forbidden lengths |
|
| Authors: | Alexandre Dolgui Mikhail Y. Kovalyov Alain Quilliot |
| Affiliation: | 1. IMT Atlantique, LS2N, CNRS, Nantes, France;2. United Institute of Informatics Problems, National Academy of Sciences of Belarus, Minsk, Belarus;3. LIMOS, UMR CNRS 6158, Bat. ISIMA, Université Blaise Pascal, Aubiere, France |
| Abstract: | We study new decision and optimization problems of finding a simple path between two given vertices in an arc weighted directed multigraph such that the path length is equal to a given number or it does not fall into the given forbidden intervals (gaps). A fairly complete computational complexity classification is provided and exact and approximation algorithms are suggested. |
| Keywords: | approximation computational complexity exact path length forbidden path length longest path problem shortest path problem |