Spider Covers and Their Applications
المؤلفون المشاركون
De Santis, Filomena
Vaccaro, Ugo
Negro, Alberto
Hammar, Mikael
Gargano, Luisa
المصدر
العدد
المجلد 2012، العدد 2012 (31 ديسمبر/كانون الأول 2012)، ص ص. 1-11، 11ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2012-11-28
دولة النشر
مصر
عدد الصفحات
11
التخصصات الرئيسية
الملخص EN
We introduce two new combinatorial optimization problems: the Maximum Spider Problem and the Spider Cover Problem; we study their approximability and illustrate their applications.
In these problems we are given a directed graph G=(V,E), a distinguished vertex s, and a family D of subsets of vertices.
A spider centered at vertex s is a collection of arc-disjoint paths all starting at s but ending into pairwise distinct vertices.
We say that a spider covers a subset of vertices X if at least one of the endpoints of the paths constituting the spider other than s belongs to X.
In the Maximum Spider Problem the goal is to find a spider centered at s that covers the maximum number of elements of the family D.
Conversely, the Spider Cover Problem consists of finding the minimum number of spiders centered at s that covers all subsets in D.
We motivate the study of the Maximum Spider and Spider Cover Problems by pointing out a variety of applications.
We show that a natural greedy algorithm gives a 2-approximation algorithm for the Maximum Spider Problem and a (log|?|+1)-approximation algorithm for the Spider Cover Problem.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
De Santis, Filomena& Gargano, Luisa& Hammar, Mikael& Negro, Alberto& Vaccaro, Ugo. 2012. Spider Covers and Their Applications. ISRN Discrete Mathematics،Vol. 2012, no. 2012, pp.1-11.
https://search.emarefa.net/detail/BIM-464648
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
De Santis, Filomena…[et al.]. Spider Covers and Their Applications. ISRN Discrete Mathematics No. 2012 (2012), pp.1-11.
https://search.emarefa.net/detail/BIM-464648
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
De Santis, Filomena& Gargano, Luisa& Hammar, Mikael& Negro, Alberto& Vaccaro, Ugo. Spider Covers and Their Applications. ISRN Discrete Mathematics. 2012. Vol. 2012, no. 2012, pp.1-11.
https://search.emarefa.net/detail/BIM-464648
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-464648
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر