کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
7543427 1489486 2018 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
ترجمه فارسی عنوان
پیچیدگی محاسباتی مشکلات مؤثر مجموعه ای برای موارد با مین های محدود از ماتریس محدود
کلمات کلیدی
برنامه ریزی خطی بولی غلبه بر مشکل مجموعه، ماتریکس کوچک، الگوریتم کارآمد،
ترجمه چکیده
ما فرمولبندی های برنامه ریزی خطی ریشه ای از رأس و لبه را در نظر می گیریم و به حل مسئله چند جمله ای زمان برای کلاس های گراف با ماتریس های محدود که دارای تعداد محدودی از آنها در مقدار مطلق است ثابت می کنیم.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش مقاله
پیچیدگی محاسباتی مشکلات مؤثر مجموعه ای برای موارد با مین های محدود از ماتریس محدود
چکیده انگلیسی
We consider boolean linear programming formulations of the vertex and edge dominating set problems and prove their polynomial-time solvability for classes of graphs with constraint matrices having bounded minors in the absolute value.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 29, August 2018, Pages 103-110
نویسندگان
, ,