A Linear Time Algorithm for a Variant of the MAX CUT Problem in Series Parallel Graphs
المؤلف
المصدر
Advances in Operations Research
العدد
المجلد 2017، العدد 2017 (31 ديسمبر/كانون الأول 2017)، ص ص. 1-4، 4ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2017-12-10
دولة النشر
مصر
عدد الصفحات
4
التخصصات الرئيسية
تكنولوجيا المعلومات وعلم الحاسوب
الملخص EN
Given a graph G=V,E, a connected sides cut U,V\U or δU is the set of edges of E linking all vertices of U to all vertices of V\U such that the induced subgraphs GU and GV\U are connected.
Given a positive weight function w defined on E, the maximum connected sides cut problem (MAX CS CUT) is to find a connected sides cut Ω such that wΩ is maximum.
MAX CS CUT is NP-hard.
In this paper, we give a linear time algorithm to solve MAX CS CUT for series parallel graphs.
We deduce a linear time algorithm for the minimum cut problem in the same class of graphs without computing the maximum flow.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Chaourar, Brahim. 2017. A Linear Time Algorithm for a Variant of the MAX CUT Problem in Series Parallel Graphs. Advances in Operations Research،Vol. 2017, no. 2017, pp.1-4.
https://search.emarefa.net/detail/BIM-1125209
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Chaourar, Brahim. A Linear Time Algorithm for a Variant of the MAX CUT Problem in Series Parallel Graphs. Advances in Operations Research No. 2017 (2017), pp.1-4.
https://search.emarefa.net/detail/BIM-1125209
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Chaourar, Brahim. A Linear Time Algorithm for a Variant of the MAX CUT Problem in Series Parallel Graphs. Advances in Operations Research. 2017. Vol. 2017, no. 2017, pp.1-4.
https://search.emarefa.net/detail/BIM-1125209
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1125209
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر