| Article ID: | iaor2005931 |
| Country: | Netherlands |
| Volume: | 32 |
| Issue: | 4 |
| Start Page Number: | 331 |
| End Page Number: | 335 |
| Publication Date: | Jul 2004 |
| Journal: | Operations Research Letters |
| Authors: | Kis Tams |
| Keywords: | combinatorial analysis |
In this note we give an easier proof of the known result that the car sequencing problem is NP-hard, and point out that it is NP-hard in the strong sense. We show that a previous claim of NP-completeness is incorrect, and instead we give a sufficient condition of membership of NP. We also provide a pseudo-polynomial algorithm for a special case.