首页 | 本学科首页   官方微博 | 高级检索  
     


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
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号