Hitting Diamonds and Growing Cacti

Details Hitting Diamonds and Growing Cacti Hitting Diamonds and Growing Cacti

2009-11-23

arxiv.org/abs/0911.4366v2

Computer Science

Data Structures and Algorithms

v2: several minor changes.

Scientific paper

We consider the following NP-hard problem: in a weighted graph, find a minimum cost set of vertices whose removal leaves a graph in which no two cycles share an edge. We obtain a constant-factor approximation algorithm, based on the primal-dual method. Moreover, we show that the integrality gap of the natural LP relaxation of the problem is \Theta(\log n), where n denotes the number of vertices in the graph.

Affiliated with

Also associated with

No associations

Rating

Hitting Diamonds and Growing Cacti does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hitting Diamonds and Growing Cacti, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hitting Diamonds and Growing Cacti will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-173121