| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652687 | Electronic Notes in Discrete Mathematics | 2008 | 6 Pages |
Abstract
We consider a track assignment problem in a train depot leading to an online bounded coloring problem on permutation graphs or on overlap graphs. For permutation graphs we study the competitiveness of a First Fit-based algorithm and we show it matches the competitive ratio of the problem. For overlap graphs, even the unbounded case does not admit a constant competitive ratio.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
