Complexity Of The Single Vehicle Scheduling Problem On Graphs

DOI10.1080/03155986.1997.11732334zbMath0894.90081OpenAlexW151090950MaRDI QIDQ4380541

Toshihide Ibaraki, Hiroshi Nagamochi, Koji Mochizuki

Publication date: 7 September 1998

Published in: INFOR: Information Systems and Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/03155986.1997.11732334

zbMATH Keywords

strong NP-hardnessvehicle scheduling

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Transportation, logistics and supply chain management (90B06) Deterministic scheduling theory in operations research (90B35)

Related Items (8)

An approximability result of the multi-vehicle scheduling problem on a path with release and handling times ⋮ Linear time approximation schemes for vehicle scheduling problems ⋮ 2-approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times. ⋮ Scheduling on a graph with release times ⋮ Approximation algorithms for single vehicle scheduling problems with release and service times on a tree or cycle ⋮ Improved algorithms for single vehicle scheduling on tree/cycle networks ⋮ A faster 2-approximation algorithm for the minmax \(p\)-traveling salesmen problem on a tree ⋮ Vehicle scheduling problems with two agents on a line

This page was built for publication: Complexity Of The Single Vehicle Scheduling Problem On Graphs