We consider the two problems of finding the maximum number of node disjoint triangles and edge disjoint triangles in an undirected graph. We show that the first (resp. second) problem is polynomially solvable if the maximum degree of the input graph is at most 3 (resp. 4), whereas it is APX-hard for general graphs and NP-hard for planar graphs if the maximum degree is 4 (resp. 5) or more.
Packing Triangles in Bounded Degree Graphs / Caprara, Alberto; Rizzi, Romeo. - ELETTRONICO. - (2002), pp. 1-9.
Packing Triangles in Bounded Degree Graphs
Rizzi, Romeo
2002-01-01
Abstract
We consider the two problems of finding the maximum number of node disjoint triangles and edge disjoint triangles in an undirected graph. We show that the first (resp. second) problem is polynomially solvable if the maximum degree of the input graph is at most 3 (resp. 4), whereas it is APX-hard for general graphs and NP-hard for planar graphs if the maximum degree is 4 (resp. 5) or more.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
99.pdf
accesso aperto
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
514.86 kB
Formato
Adobe PDF
|
514.86 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione
