PT Journal
AU Paluch, S
TI Bus Scheduling as a Graph Coloring Problem
SO Communications - Scientific Letters of the University of Zilina
PY 2003
BP 16
EP 20
VL 5
IS 4
DI 10.26552/com.C.2003.4.16-20
WP https://komunikacie.uniza.sk/artkey/csl-200304-0003.php
DE no keywords
SN 13354205
AB The fundamental vehicle-scheduling problem (VSP) is usually formulated as a matching problem for which there exists a polynomial algorithm. The formulation of VSP as a graph coloring problem may seem not to be practical since a graph coloring problem is NP-hard and it is not a good idea to solve a polynomial problem using a non polynomial algorithm. However, no polynomial algorithms have been found for generalizations of VSP and hence the graph coloring formulation offers good approximation algorithms for their solution.
ER