A 4 + ϵ approximation for k-connected subgraphs

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


We obtain approximation ratio [Formula presented] for the (undirected) k-CONNECTED SUBGRAPH problem, where [Formula presented] is the largest integer such that 2ℓ−1k2ℓ+1≤n. For large values of n this improves the ratio 6 of Cheriyan and Végh [4] when n≥k3 (the case ℓ=1). Our result implies an fpt-approximation ratio 4+ϵ that matches (up to the “+ϵ” term) the best known ratio 4 for k=6,7 for both the general and the easier augmentation versions of the problem. Similar results are shown for the problem of covering an arbitrary symmetric crossing supermodular biset function.

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)64-75
عدد الصفحات12
دوريةJournal of Computer and System Sciences
مستوى الصوت123
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - فبراير 2022

ملاحظة ببليوغرافية

Publisher Copyright:
© 2021 Elsevier Inc.


أدرس بدقة موضوعات البحث “A 4 + ϵ approximation for k-connected subgraphs'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا