ملخص: On considère le problème combinatoire suivant. Étant donnée une matrice binaire A, chercher une permutation de ses colonnes de maniéré à ce que le nombre de blocs de 1 consécutifs soit minimal. On propose une première réduction polynomiale de ce problème à celui d'une chaîne hamiltonienne de poids maximum. Une réduction réciproque est également préposée; comme cette réduction préserve l'approximation et puisque on montre que l'on ne peut approximer absolument le problème de la chaîne hamiltonienne de poids maximum, on ne peut non plus approximer absolument le problème posé. Une deuxième réduction polynomiale de ce dernier au problème du voyageur de commerce est montée.

Annaba:
لغة: فرنسية
الوصف المادي: 33 p. ill. ;30 cm.
الشهادة: Magister
مؤسسة مناقشة الرسالة: Annaba, Université Badji Mokhtar. Institut de Mathématiques
تخصص: Mathématiques
الفهرس العشري 510 .الرياضيات
الموضوع الرياضيات

الكلمات الدالة:
minimisation du nombre de blocs
matrice binaire

ملاحظة: Bibliogr. pp.32-33