کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1143004 957172 2007 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The path partition problem and related problems in bipartite graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The path partition problem and related problems in bipartite graphs
چکیده انگلیسی

We prove that it is NP-complete to decide whether a bipartite graph of maximum degree three on nk vertices can be partitioned into n paths of length k. Finally, we propose some approximation and inapproximation results for several related problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 35, Issue 5, September 2007, Pages 677–684
نویسندگان
, ,