Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation
المؤلفون المشاركون
Suebsriwichai, A.
Mouktonglang, Thanasak
المصدر
Journal of Applied Mathematics
العدد
المجلد 2017، العدد 2017 (31 ديسمبر/كانون الأول 2017)، ص ص. 1-7، 7ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2017-05-08
دولة النشر
مصر
عدد الصفحات
7
التخصصات الرئيسية
الملخص EN
The crossing number of graph G is the minimum number of edges crossing in any drawing of G in a plane.
In this paper we describe a method of finding the bound of 2-page fixed linear crossing number of G.
We consider a conflict graph G′ of G.
Then, instead of minimizing the crossing number of G, we show that it is equivalent to maximize the weight of a cut of G′.
We formulate the original problem into the MAXCUT problem.
We consider a semidefinite relaxation of the MAXCUT problem.
An example of a case where G is hypercube is explicitly shown to obtain an upper bound.
The numerical results confirm the effectiveness of the approximation.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Suebsriwichai, A.& Mouktonglang, Thanasak. 2017. Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation. Journal of Applied Mathematics،Vol. 2017, no. 2017, pp.1-7.
https://search.emarefa.net/detail/BIM-1170022
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Suebsriwichai, A.& Mouktonglang, Thanasak. Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation. Journal of Applied Mathematics No. 2017 (2017), pp.1-7.
https://search.emarefa.net/detail/BIM-1170022
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Suebsriwichai, A.& Mouktonglang, Thanasak. Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation. Journal of Applied Mathematics. 2017. Vol. 2017, no. 2017, pp.1-7.
https://search.emarefa.net/detail/BIM-1170022
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-1170022
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر