کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420848 683991 2008 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Covering symmetric semi-monotone functions
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Covering symmetric semi-monotone functions
چکیده انگلیسی

We define a new set of functions called semi-monotone, a subclass of skew-supermodular functions. We show that the problem of augmenting a given graph to cover a symmetric semi-monotone function is NP-complete if all the values of the function are in {0,1}{0,1} and we provide a minimax theorem if all the values of the function are different from 1. Our problem is equivalent to the node to area augmentation problem. Our contribution is to provide a significantly simpler and shorter proof.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 1, 1 January 2008, Pages 138–144
نویسندگان
, ,