Codes identifiants dans les graphes: Cas de Chemins et de Circuits
Ahmed Semri, Hillal Touati
كلية الرياضيات-جامعة العلوم والتكنولوجيا هواري بومدين - الجزائر · الجزائر
الموضوعات
علوم تطبيقية وتكنولوجية
الملخص
La notion de codes identifiants a été définie pour la première fois par M. Karpovsky, K. Chakrabarty et L. Levitin en 1998 pour modéliser un problème de détection de processeurs défectueux dans des réseaux multiprocesseurs. Ce concept a, depuis, été repris par de nombreuses équipes de recherche engendrant une littérature abondante. Dans ce mémoire, nous avons abordé le problème de recherche de code identifiant de cardinalité minimum, un problème appartenant à la classe des problèmes NP-difficiles. Peu de résultats sont connus dans le cas de graphes orientés, ceci nous a amené à étudier les codes identifiants dans ce type de graphes. Dans notre travail, nous nous sommes intéressé à l'étude de ce problème dans le cas de chemins et de circuits. Nous avons pu déterminer la cardinalité minimum d'un code 1 et 2-identifiant aussi bien pour un chemin que pour un circuit
روابط وملفات
التعريف والنوع
- رقم الوثيقة
- 0118dd54-5b88-4d44-a44b-b0d559d4d998
- رقم العقد
- 0
- نوع الوسائط
- Crawler
- نوع المحتوى
- الرسائل العلمية
- صيغة المصدر
- رسائل ماجيستير
- نوع الملف
- word
- أسماء الملفات
- 1376723_1.docx, 1376723_2.pdf
بيانات النشر
- ألقاب المؤلفين
- [{"name_ar":"Ahmed Semri","title_ar":"اشراف","title_en":"Supervision"},{"name_ar":"Hillal Touati","title_ar":"اعداد","title_en":"Preparation"}]
- اللغة
- French
المصدر والدورية
- اسم المصدر
- Codes identifiants dans les graphes: Cas de Chemins et de Circuits
المحتوى والصفحات
- عدد الصفحات
- 0
- ترجمة الملخص
- Identifying codes were first introduced by Karpovsky, Chakrabarty, Levitin.Their motivation for identification comes from locating faulty processors in a multi-processor system. In general, finding an optimal identifying codes is known to be an NP-complete problem.Nowadays, this concept is taken by numerous research team, what produced plentiful literature .In this thesis we reach the problem of identifying code. Few results are known in the case of directed graphs, this led us to study this problem in this type of graphs.In our work, we investigate the identifing code problem in paths and circuits and we could determine the smallest cardinality of 1 and 2-identifying codes.
- كلمات الباحثين
- Circuits intégrés, Graphes, orientés, Théorie des Graphes
إشراف وإعداد
- الإشراف
- Ahmed Semri
- الإعداد
- Hillal Touati
الاقتباسات الببليوغرافية
APA
MLA