RT Journal Article
SR Electronic
A1 Paluch, Stanislav
T1 Bus Scheduling as a Graph Coloring Problem
JF Communications - Scientific Letters of the University of Zilina
YR 2003
VO 5
IS 4
SP 16
OP 20
DO 10.26552/com.C.2003.4.16-20
UL https://komunikacie.uniza.sk/artkey/csl-200304-0003.php
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.