کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650603 | 1342494 | 2008 | 17 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Packing triangles in low degree graphs and indifference graphs Packing triangles in low degree graphs and indifference graphs](/preview/png/4650603.png)
We consider the problems of finding the maximum number of vertex-disjoint triangles (VTPVTP) and edge-disjoint triangles (ETPETP) in a simple graph. Both problems are NPNP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2+ɛ3/2+ɛ, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68–72]. We present improvements on the approximation ratio for restricted cases of VTPVTP and ETPETP that are known to be APXAPX-hard: we give an approximation algorithm for VTPVTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETPETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTPVTP on the class of indifference graphs.
Journal: Discrete Mathematics - Volume 308, Issue 8, 28 April 2008, Pages 1455–1471