![](/images/graphics-bg.png)
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"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
![](/images/ebook-kashef.png)
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر
![](/images/kashef-image.png)