کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9667542 | 863757 | 2005 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Phase transition and finite-size scaling in the vertex-cover problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
شیمی
شیمی تئوریک و عملی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
NP-complete problems play a fundamental role in theoretical computer science. Recently, phase transitions were discovered in such problems, when studying suitably parameterized random ensembles. By applying concepts and methods from statistical physics, it is possible to understand these models and the phase transitions which occur. Here, we consider the vertex-cover problem, one of the six “basic” NP-complete problems. We describe the phase transition and the running time of an exact algorithm around the phase transition. To investigate how this transition resembles a phase transition in physical systems, we apply finite-size scaling and we study a correlation-length like quantity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Physics Communications - Volume 169, Issues 1â3, 1 July 2005, Pages 234-237
Journal: Computer Physics Communications - Volume 169, Issues 1â3, 1 July 2005, Pages 234-237
نویسندگان
Alexander K. Hartmann, Wolfgang Barthel, Martin Weigt,