کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
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
کلمات کلیدی
نمودار بدون 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
نویسندگان
, ,