کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646583 | 1342307 | 2016 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On computational complexity of length embeddability of graphs
ترجمه فارسی عنوان
در پیچیدگی محاسباتی ابعاد طول نمودار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیچیدگی محاسباتی، تعبیه گراف، نمودار فاصله
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A graph GG is embeddable in RdRd if the vertices of GG can be assigned to points of RdRd in such a way that all pairs of adjacent vertices are at distance 1. We show that verifying embeddability of a given graph in RdRd is NP-hard in the case d>2d>2 for all reasonable notions of embeddability.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 11, 6 November 2016, Pages 2605–2612
Journal: Discrete Mathematics - Volume 339, Issue 11, 6 November 2016, Pages 2605–2612
نویسندگان
Mikhail Tikhomirov,