کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903463 | 1632568 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimizing Profile of Graphs Using a Hybrid Simulating Annealing Algorithm
ترجمه فارسی عنوان
کمینه کردن مشخصات نمودارها با استفاده از الگوریتم انحلال شبیه سازی ترکیبی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
توالی اسپکتروم، کمینه سازی مشخصات، شبیه سازی آنیل ماتریسهای ضخیم
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The profile minimization problem is a graph layout problem that consists of finding a linear arrangement (labeling) of vertices of a graph such that the sum of profiles of all vertices is minimum. The profile of a vertex can be defined as the difference of the position of its left most neighbor and the position of that vertex in the linear arrangement. It is an NP-complete problem with applications in the areas where the reordering of rows and columns of a sparse matrix is required in order to reduce the storage space. In this work, we propose a hybrid simulated annealing algorithm with the aim of profile reduction of a given graph by incorporating spectral sequencing for generating the initial solution. Experiments conducted on some benchmark graphs show that our algorithm outperforms the best existing algorithm in some cases and is comparable for rest of the instances. It also attains the optimal values for some classes of graphs with known optimal results.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 63, December 2017, Pages 381-388
Journal: Electronic Notes in Discrete Mathematics - Volume 63, December 2017, Pages 381-388
نویسندگان
Yogita Singh Kardam, Kamal Srivastava, Reeti Sharma,