کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871360 1440184 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
ترجمه فارسی عنوان
الگوریتم های ساده زمان خطی برای شمارش مجموعه های مستقل در گراف های فاصله ای ارثی
کلمات کلیدی
نمودارهای ارثی، شمارش مشکل مجموعه مستقل، مجموعه مستقل مستقل، مستقل کامل مجموعه غالب، الگوریتم های خطی زمان،
ترجمه چکیده
گراف متصل شده، اگر هر دو رأس در همه زیرگراف های القا شده متصل به آن، همان فاصله را داشته باشند، فاصله ای است که ارثی است. این مقاله یک روش یکپارچه برای طراحی الگوریتم های خطی زمان برای شمارش مجموعه های مستقل و دو نوع آنها، مجموعه های مستقل مستقل و مجموعه های مستقل مستقل کامل در نمودار های فاصله ای ارثی ارائه می دهد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش مقاله
الگوریتم های ساده زمان خطی برای شمارش مجموعه های مستقل در گراف های فاصله ای ارثی
چکیده انگلیسی
A connected graph is distance-hereditary if any two vertices have the same distance in all of its connected induced subgraphs. This paper proposes a unified method for designing linear-time algorithms for counting independent sets and their two variants, independent dominating sets and independent perfect dominating sets, in distance-hereditary graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 239, 20 April 2018, Pages 144-153
نویسندگان
,