Geodesic
Packing triangles in low degree graphs and indifference graphs
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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 from a more general algorithm for set packing obtained by Hurkens and Schrijver in 1989. 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. 
@article{DMTCS_2005_special_250_a17,
     author = {Mani\'c, Gordana and Wakabayashi, Yoshiko},
     title = {Packing triangles in low degree graphs and indifference graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3408},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3408/}
}
TY  - JOUR
AU  - Manić, Gordana
AU  - Wakabayashi, Yoshiko
TI  - Packing triangles in low degree graphs and indifference graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3408/
DO  - 10.46298/dmtcs.3408
LA  - en
ID  - DMTCS_2005_special_250_a17
ER  - 
%0 Journal Article
%A Manić, Gordana
%A Wakabayashi, Yoshiko
%T Packing triangles in low degree graphs and indifference graphs
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3408/
%R 10.46298/dmtcs.3408
%G en
%F DMTCS_2005_special_250_a17
Manić, Gordana; Wakabayashi, Yoshiko. Packing triangles in low degree graphs and indifference graphs. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3408. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3408/

Cité par Sources :