Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
57--62
Opis fizyczny
Bibliogr 6 poz., rys.
Twórcy
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BSW9-0007-1312