کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141414 | 1489495 | 2016 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An O(nm) algorithm for the weighted stable set problem in {claw, net}-free graphs with α(G)≥4α(G)≥4
ترجمه فارسی عنوان
یک الگوریتم O (نانومتر) برای مسئله مجموعه ای پایدار موزون در نمودار بدون {claw، شبکه} با α (G) ≥4α (G) ≥4
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار بدون claw ؛ نمودار بدون شبکه . مجموعه پایدار؛ تطابق
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
چکیده انگلیسی
In this paper we show that a connected {claw, net}-free graph G(V,E)G(V,E) with α(G)≥4α(G)≥4 is the union of a strongly bisimplicial clique QQ and at most two clique-strips . A clique is strongly bisimplicial if its neighborhood is partitioned into two cliques which are mutually non-adjacent and a clique-strip is a sequence of cliques {H0,…,Hp}{H0,…,Hp} with the property that HiHi is adjacent only to Hi−1Hi−1 and Hi+1Hi+1. By exploiting such a structure we show how to solve the Maximum Weight Stable Set Problem in such a graph in time O(|V||E|), improving the previous complexity bound of O(|V||E|)O(|V||E|).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 19, February 2016, Pages 63–78
Journal: Discrete Optimization - Volume 19, February 2016, Pages 63–78
نویسندگان
Paolo Nobili, Antonio Sassano,