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
  • مقاله ریاضیات گسسته و ترکیبیات
  • ترجمه مقاله ریاضیات گسسته و ترکیبیات
سفارش ترجمه مقاله و کتاب - شروع کنید

با استفاده از افزونه دانلود فایرفاکس چکیده مقالات به صورت خودکار تشخیص داده شده و دکمه دانلود فری‌پیپر در صفحه چکیده نمایش داده می شود.