کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10151231 | 685009 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Computing square roots of graphs with low maximum degree
ترجمه فارسی عنوان
محاسبه ریشه های مربعی از نمودار ها با درجه پایین ترین درجه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ریشه دوم، نمودار درجه محدود الگوریتم چندجمله ای،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. We prove that Square Root is O(n)-time solvable for graphs of maximum degree 5 and O(n4)-time solvable for graphs of maximum degree at most 6.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 248, 30 October 2018, Pages 93-101
Journal: Discrete Applied Mathematics - Volume 248, 30 October 2018, Pages 93-101
نویسندگان
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, Anthony Stewart,