Approximation algorithms for cycle packing problems

Michael Krivelevich, Zeev Nutov, Raphael Yuster

פרסום מחקרי: תוצר מחקר מכנסהרצאהביקורת עמיתים


The cycle packing number vc(G) of a graph G is the maximum number of pairwise edge-disjoint cycles in G. Computing vc(G) is an NP-hard problem. We present approximation algorithms for computing v c(G) in both the undirected and directed cases. In the undirected case we analyze the modified greedy algorithm suggested in [4] and show that it has approximation ratio O(√log n) where n = |V(G)|, and this is tight. This improves upon the previous O(log n) upper bound for the approximation ratio of this algorithm. In the directed case we present a √n-approximation algorithm. Finally, we give an O(n2/3)-approximation algorithm for the problem of rinding a maximum number of edge-disjoint cycles that intersect a specified subset S of vertices. Our approximation ratios are the currently best known ones and, in addition, provide bounds on the integrality gap of standard LP-relaxations to these problems.

שפה מקוריתאנגלית
מספר עמודים6
סטטוס פרסוםפורסם - 2005
אירועSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, ארצות הברית
משך הזמן: 23 ינו׳ 200525 ינו׳ 2005


כנסSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
מדינה/אזורארצות הברית
עירVancouver, BC

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximation algorithms for cycle packing problems'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי