A new Integer Linear Programming and Quadratically Constrained Quadratic Programming Formulation for Vertex Bisection Minimization Problem

• Autorzy: Jain P. , Saran G. , Srivastava K.

Identyfikatory

DOI

10.14313/JAMRIS_1-2016/9

• Języki publikacji: EN

Abstrakty

EN

Vertex Bisection Minimization problem (VBMP) consists of partitioning a vertex set V of graph G = (V, E) into two sets B and B′ where ∣B∣ = [\v|/2] such that vertex width (VW) is minimized where vertex width is defined as the number of vertices in B which are adjacent to at least one vertex in B′. It is an NP-complete problem in general. VBMP has applications in fault tolerance and is related to the complexity of sending messages to processors in interconnection networks via vertex disjoint paths. In this paper, we have proposed a new integer linear programming (ILP) and quadratically constrained quadratic programming (QCQP) formulation for VBMP. Both of them require number of variables and constraints lesser than existing ILPs and QCQP. We have also implemented ILP and obtained optimal results for various classes of graphs. The result of the experiments with the benchmark graphs shows that the proposed model outperforms the state of the art. Moreover, proposed model obtains optimal result for all the benchmark graphs.

Słowa kluczowe

EN

vertex bisection minimization; Integer Linear Programming; quadratic programming

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2016
• Tom: Vol. 10, No. 1
• Strony: 69--73
• Opis fizyczny: Bibliogr. 10 poz., tab.

Twórcy

autor

Jain P.

• Department of Mathematics, Dayalbagh Educational Institute, Agra, India. Tel: [phone]

autor

Saran G.

• Department of Mathematics, Dayalbagh Educational Institute, Agra, India. Tel: [phone]

autor

Srivastava K.

• Department of Mathematics, Dayalbagh Educational Institute, Agra, India. Tel: [phone]

Bibliografia

• [1] Brandes U., Fleischer D., “Vertex Bisection is Hard, too”, Journal of Graph Algorithms and Applications, vol. 13, no. 2, 2009, 119–131. DOI: 10.7155/jgaa.00179.
• [2] Diaz J., Petit J., Serna M., “A Survey of Graph Layout Problems”, ACM Computing Surveys, vol. 34, no. 3, 2002, 313–356. DOI: 10.1145/568522.568523.
• [3] Petit J., “Addenda to the Survey of Layout Problems”, Bulletin of the European Association for Theoretical Computer Science (EATCS), no. 105, 2011, 177–201.
• [4] Fraire H., David J., Villanueva T., et al., “Exact Methods for the Vertex Bisection Problem“. In: Recent Advances on Hybrid Approaches for Designing Intelligent Systems, ed. by: O. Castillo, P. Melin, W. Pedrycz, J. Kacprzyk, chapter 40, series: Studies in Computational Intelligence vol. 547, 2014, 567–577. DOI: 10.1007/978-3-319-05170-3_40.
• [5] Vazirani V.V., Approximation Algorithms, Springer 2003. DOI: 10.1007/978-3-662-04565-7.
• [6] Diaby M., “The Travelling Salesman Problem: Linear Programming Formulation”, WSEAS Transactions on Mathematics, no. 6, 2007, 745–754.
• [7] Frieze A., Jerrum M., “Improved Approximation Algorithms for Max k-cut and Max Bisection“, Algorithmica, vol. 18, no. 1, 1997, 67–81. DOI: 10.1007/BF02523688.
• [8] Duarte A., Escudero L.F., Marti R., et al., “Variable Neighborhood Search for the Vertex Separation Problem“, Computers and Operations Research, vol. 39, no. 12, 2012, 3247–3255. DOI: 10.1016/j.cor.2012.04.017.
• [9] Loces M.C.L., Garcia N.C., Huacuja H.J.F., et al., “A New Integer Linear Programming Model for the Cutwidth Minimization Problem of a Connected Undirected Graph“, In: Recent Advances on Hybrid Approaches for Designing Intelligent Systems, ed. by: O. Castillo, P. Melin, W. Pedrycz, J. Kacprzyk, chapter 40, series: Studies in Computational Intelligence vol. 547, 2014, 509–517. DOI: 10.1007/978-3-319-05170-3_35.
• [10] Luttamaguzi J., Pelsmajer, M., Shen, Z., Yang, B., Integer Programming Solutions for Several Optimization Problems in Graph Theory. Technical report, DIMACS 2005.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.