𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of the car sequencing problem

✍ Scribed by Tamás Kis

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
190 KB
Volume
32
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

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 su cient condition of membership of NP. We also provide a pseudo-polynomial algorithm for a special case.

📜 SIMILAR VOLUMES

On the complexity of the pancake problem
On the complexity of the pancake problem
✍ Fuxiang Yu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

## Abstract We study the computational complexity of finding a line that bisects simultaneously two sets in the two‐dimensional plane, called __the pancake problem__, using the oracle Turing machine model of Ko. We also study the basic problem of bisecting a set at a given direction. Our main resul

On the complexity of recursion in proble
On the complexity of recursion in problem-solving
✍ M.C. Er 📂 Article 📅 1984 🏛 Elsevier Science ⚖ 426 KB

The importance of paying attention to the complexity of recursion in problem solving is stressed. Many ill-founded beliefs and doctrines on constructing recursive algorithms are challenged. The Tower of Hanoi problem and its variant are used as concrete examples for illustrating that many seemingly