کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438598 690296 2007 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
چکیده انگلیسی

We prove that the max-cut and max-bisection problems are NP-hard on unit disk graphs. We also show that λ-precision graphs are planar for and give a dichotomy theorem for max-cut computational complexity on λ-precision unit disk graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 377, Issues 1–3, 31 May 2007, Pages 271-276