Packing triangles in low degree graphs and indifference graphs
Packing triangles in low degree graphs and indifference graphs
复制标题
DOI：
10.1016/j.disc.2007.07.100
复制
发表时间：
2008-04
期刊：
影响因子：
--
通讯作者：
G. Manic;Yoshiko Wakabayashi
中科院分区：
文献类型：
--
作者：
G. Manic;Yoshiko Wakabayashi
我们考虑了在简单图中求最大顶点不交三角形(VTP)和边不交三角形(ETP)的问题。这两个问题都是NP难的。到目前为止，对于这些问题具有最佳逼近比的算法具有比3/2+ɛ，这是由Hurkens和Schrijver[关于每t个集合都有SDR的集合系统的大小]得到的更一般的集合布局算法的结果，并应用于布局问题的启发式的最坏情况比，SIAM J.离散数学。2(1)(1989)68-72]。我们对已知为APX-Hard的VTP和ETP的限制情形的逼近比进行了改进：我们给出了VTP在最大度为4且比略小于1.2的图上的逼近算法，以及在最大度为5且比为4/3的图上的逼近算法。我们还给出了无差图类上VTP的精确线性时间算法。
We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 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 VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs.