On an NP-hard sorting problem

• Autorzy: Giaro K.
• Języki publikacji: EN

Abstrakty

EN

We show that the following problem: given a sequence of numbers; arrange these numbers into order using as few interchanges as possible cannot be solved in polynomial time, unless P=NP.

Słowa kluczowe

EN

sorting problem; NP-hardness; flexible manufacturing systems

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2001
• Tom: Vol. 11, no. 1/2
• Strony: 57--62
• Opis fizyczny: Bibliogr 6 poz., rys.

Twórcy

autor

Giaro K.

• Technical University of Gdansk, Foundations of Informatics Dept. Narutowicza 11/12, 80-952 Gdansk, Pola

Bibliografia

• [1] V. Bafna and P. Pevzner: Sorting by transpositions. SIAM J. Discrete Math., 11 (1998), 224-240.
• [2] A. Caprara: Sorting by reversals is difficult. Proc. RECOMB’97, ACM Press, New York, (1997).
• [3] S. Even, A. Itai and A. Shamir: On the complexity of timetable and multicommodity flow problems. SIAM J. on Computing, 5 (1976), 691-703.
• [4] M. Garey and D. S. Johnson: Computers and Intractability. A Guide to the Theory of NP-Completness. Freeman, New York, 1979.
• [5] M. Garey, D. Johnson and L. Stockmeyer: Some simplified NP-complete graph problems. Theor. Comput. Sci., 1 (1976), 237 - 267.
• [6] K. Giaro and M. Kubale: Edge-chromatic sum of trees and bounded cyclicity graphs. Inf. Process. Lett., 75 (2000), 65-69.