Bound for the 2-Page Fixed Linear Crossing Number of Hypercube Graph via SDP Relaxation
Joint Authors
Suebsriwichai, A.
Mouktonglang, Thanasak
Source
Journal of Applied Mathematics
Issue
Vol. 2017, Issue 2017 (31 Dec. 2017), pp.1-7, 7 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2017-05-08
Country of Publication
Egypt
No. of Pages
7
Main Subjects
Abstract 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.
American Psychological Association (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
Modern Language Association (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
American Medical Association (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
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1170022