Packing triangles in low degree graphs and indifference graphs

Packing triangles in low degree graphs and indifference graphs

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 guarantee known so far for these problems has ratio $3/2 + ɛ$, a result that follows fro...

Full description

Bibliographic Details
Main Authors: Gordana Manić, Yoshiko Wakabayashi
Format: Article
Language:English
Published: Discrete Mathematics & Theoretical Computer Science 2005-01-01
Series:Discrete Mathematics & Theoretical Computer Science
Subjects:
triangle packing
approximation algorithm
polynomial algorithm
low degree graph
indifference graph
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
Online Access:https://dmtcs.episciences.org/3408/pdf

Internet

https://dmtcs.episciences.org/3408/pdf

Similar Items