Pseudo Polynomial Time Algorithms for Optimal Longcut Route Selection

Yuichi SUDO  Toshimitsu MASUZAWA  Gen MOTOYOSHI  Tutomu MURASE  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D    No.3    pp.607-616
Publication Date: 2015/03/01
Publicized: 2014/11/25
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014EDP7278
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
longcut route,  route selection,  NP-hardness,  pseudo polynomial time algorithm,  

Full Text: PDF(805.5KB)>>
Buy this Article


Summary: 
Users of wireless mobile devices need Internet access not only when they stay at home or office, but also when they travel. It may be desirable for such users to select a "longcut route" from their current location to his/her destination that has longer travel time than the shortest route, but provides a better mobile wireless environment. In this paper, we formulate the above situation as the optimization problem of “optimal longcut route selection”, which requires us to find the best route concerning the wireless environment subject to a travel time constraint. For this new problem, we show NP-hardness, propose two pseudo-polynomial time algorithms, and experimental evaluation of the algorithms.

open access publishing via