view in publisher's site
- خانه
- لیست مقالات
- چکیده
Approximation algorithm for minimum connected 3-path vertex cover
A vertex subset S of a given graph G=(V,E) is called a connected k-path vertex cover (CVCPk) if every k-path of G contains at least one vertex from S, and the subgraph of G induced by S is connected. This concept has its background in the field of security and supervisory and the computation of a minimum CVCPk is NP-hard. In this paper, we give a (2α+1∕2)-approximation algorithm for MinCVCP3, where α is the performance ratio of an algorithm for MinVCP3.
الگوریتم تقریبی برای کمینه کردن پوشش راس ۳ - مسیر متصل
یک زیرمجموعه راس S از یک گراف داده‌شده G = (V، E)یک پوشش راس k - مسیر متصل (CVCPk)نامیده می‌شود اگر هر k - مسیر G شامل حداقل یک راس از S باشد و زیرگراف G القا شده توسط S متصل باشد.
این مفهوم پیشینه خود را در زمینه امنیت و نظارت دارد و محاسبه حداقل CVCPK، NP - hard است.
در این مقاله، ما یک الگوریتم تقریبی (۲ α + ۱۲)برای MinCVCP۳ ارائه می‌دهیم، که در آن α نسبت عملکرد یک الگوریتم برای MinVCP۳ است.
ترجمه شده با 
- مقاله Applied Mathematics
- ترجمه مقاله Applied Mathematics
- مقاله ریاضیات کاربردی
- ترجمه مقاله ریاضیات کاربردی
- مقاله Discrete Mathematics and Combinatorics
- ترجمه مقاله Discrete Mathematics and Combinatorics
- مقاله ریاضیات گسسته و ترکیبیات
- ترجمه مقاله ریاضیات گسسته و ترکیبیات
ترجمه کنید