PT  - JOURNAL ARTICLE
AU  - Paluch, Stanislav
TI  - Bus Scheduling as a Graph Coloring Problem
DP  - 2003 Dec 31
TA  - Communications - Scientific Letters of the University of Zilina
PG  - 16--20
VI  - 5
IP  - 4
AID - 10.26552/com.C.2003.4.16-20
IS  - 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.