کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903332 | 1632565 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Efficient heuristics for the minimum labeling global cut problem
ترجمه فارسی عنوان
اکتشافات کارآمد برای کمینه کردن مسئله برش جهانی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار های لبه برچسب جستجوی محدوده متغیر اتصال
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Let G=(V,E,L) be an edge-labeled graph. Let V be the set of vertices of G, E the set of edges, L the set of labels (colors) such that each edge eâE has an associated label L(e). The goal of the minimum labeling global cut problem (MLGCP) is to find a subset Lâ²âL of labels such that Gâ²=(V,Eâ²,L\Lâ²) is not connected and |Lâ²| is minimized. In this work, we generate random instances for the MLGCP to perform empirical tests. Also propose a set of heuristics using concepts of Genetic Algorithm and metaheuristic VNS, including some of their procedures, like two local search moves, and an auxiliary data structure to speed up the local search. Computational experiments show that the metaheuristic VNS outperforms other methods with respect to solution quality.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 66, April 2018, Pages 23-30
Journal: Electronic Notes in Discrete Mathematics - Volume 66, April 2018, Pages 23-30
نویسندگان
Thiago Gouveia da Silva, Gilberto F. de Sousa Filho, Igor A.M. Barbosa, Nenad Mladenovic, Lucidio A.F. Cabral, Luiz Satoru Ochi, Daniel Aloise,