Bus Scheduling as a Graph Coloring Problem
Bus Scheduling as a Graph Coloring Problem
Author(s): Stanislav PaluchSubject(s): Methodology and research technology, ICT Information and Communications Technologies, Transport / Logistics
Published by: Žilinská univerzita v Žilině
Keywords: Graph; Coloring Problem; Bus Scheduling;
Summary/Abstract: 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.
Journal: Komunikácie - vedecké listy Žilinskej univerzity v Žiline
- Issue Year: 5/2003
- Issue No: 4
- Page Range: 16-20
- Page Count: 5
- Language: English