Cellular processing algorithm for the vertex bisection problem: Detailed analysis and new component design

被引：4

作者：

David Teran-Villanueva, J. ^{[1
]}

Joaquin Fraire-Huacuja, Hector ^{[2
]}

Ibarra Martinez, Salvador ^{[1
]}

Cruz-Reyes, Laura ^{[2
]}

Castan Rocha, Jose Antonio ^{[1
]}

Gomez Santillan, Claudia ^{[2
]}

Laria Menchaca, Julio ^{[1
]}

机构：

[1] UAT, Tamps 89109, Ctr Univ Tampico Madero S-N, Tampico 89109, Tamps, Mexico

[2] Tecnol Nacl Mexico, ITCM, Av 1o Mayo S-No, Cd Madero 89440, Tam, Mexico

来源：

INFORMATION SCIENCES | 2019年 / 478卷

关键词：

Cellular processing algorithms; Vertex bisection problem; Metaheuristics; Algorithm performance study; DISJOINT PATHS MODE; SEARCH; IMAGE;

D O I：

10.1016/j.ins.2018.11.020

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The vertex bisection problem splits a graph G = (V, E) into two sets, L subset of V, vertical bar L vertical bar left perpendicular vertical bar V vertical bar/2 right perpendicular and R = V \ L, such that it minimizes the number of vertices in L connected to R. This problem is a combinatorial NP-hard problem with relevant applications in network communications and, currently, there is only one metaheuristic method that solves it. In this paper, we propose a Cellular Processing Algorithm (CPA) that outperforms the state of the art showing a detailed description of its components and assessing the impact of its main components. Additionally, we include the best-known solutions for the new benchmark of 137 challenging instances. The experimental study, with the new benchmark, shows that the CPA increases the number of best solutions found to 190% and decreases the time to 21% with respect to an efficiency-improved version of the state of the art algorithm. Finally, a non-parametric statistical hypothesis test confirms that the CPA outperforms statistically the efficiency-improved implementation of the state of the art algorithm. (C) 2018 Elsevier Inc. All rights reserved.

引用

页码：62 / 82

页数：21

共 32 条

[11]

Duff I., 2010, SPARSE MATRIX COLLEC

[12]

Fraire H, 2014, STUD COMPUT INTELL, V547, P567, DOI 10.1007/978-3-319-05170-3_40

[13] GOSSIPING IN VERTEX-DISJOINT PATHS MODE IN D-DIMENSIONAL GRIDS AND PLANAR GRAPHS [J].

HROMKOVIC, J ;

KLASING, R ;

STOHR, EA ;

WAGENER, H .

INFORMATION AND COMPUTATION, 1995, 123 (01) :17-28

[14] On minimizing vertex bisection using a memetic algorithm [J].

Jain, Pallavi ;

Saran, Gur ;

Srivastava, Kamal .

INFORMATION SCIENCES, 2016, 369 :765-787

[15] The relationship between the gossip complexity in vertex-disjoint paths mode and the vertex bisection width [J].

Klasing, R .

DISCRETE APPLIED MATHEMATICS, 1998, 83 (1-3) :229-246

[16] Graphicut textures:: Image and video synthesis using graph cuts [J].

Kwatra, V ;

Schödl, A ;

Essa, I ;

Turk, G ;

Bobick, A .

ACM TRANSACTIONS ON GRAPHICS, 2003, 22 (03) :277-286

[17]

Liberti L, 2009, STUD COMPUT INTELL, V203, P153

[18] EXACT AND HEURISTIC APPROACHES TO SOLVE THE INTERNET SHOPPING OPTIMIZATION PROBLEM WITH DELIVERY COSTS [J].

Lopez-Loces, Mario C. ;

Musial, Jedrzej ;

Pecero, Johnatan E. ;

Fraire-Huacuja, Hector J. ;

Blazewicz, Jacek ;

Bouvry, Pascal .

INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE, 2016, 26 (02) :391-406

[19] An effective iterated tabu search for the maximum bisection problem [J].

Ma, Fuda ;

Hao, Jin-Kao ;

Wang, Yang .

COMPUTERS & OPERATIONS RESEARCH, 2017, 81 :78-89

[20]

Malewicz G., 2010, SIGMOD, P135, DOI [10.1145/1807167.1807184, DOI 10.1145/1807167.1807184]

← 1 2 3 4 →