Packing triangles in bounded degree graphs.

DOI10.1016/S0020-0190(02)00274-0zbMath1042.68087OpenAlexW1969483202MaRDI QIDQ1853132

Romeo Rizzi, Alberto Caprara

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00274-0

zbMATH Keywords

NP-hardnessPolynomial algorithmAPX-hardnessPlanar graphsPacking triangles

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (18)

Hardness and approximation of traffic grooming ⋮ Unnamed Item ⋮ Approximate min-max relations for odd cycles in planar graphs ⋮ Restricted assignment scheduling with resource constraints ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ Triangle strings: structures for augmentation of vertex-disjoint triangle sets ⋮ AN IMPLICIT COVER PROBLEM IN WILD POPULATION STUDY ⋮ Approximation algorithms and hardness results for the clique packing problem ⋮ Packing triangles in low degree graphs and indifference graphs ⋮ Approximation algorithms and hardness results for the clique packing problem ⋮ Packing edge-disjoint cycles in graphs and the cyclomatic number ⋮ Packing disjoint cycles over vertex cuts ⋮ MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS ⋮ On packing shortest cycles in graphs ⋮ On approximating four covering and packing problems ⋮ On Approximating an Implicit Cover Problem in Biology ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• On maximal independent sets of vertices in claw-free graphs
• 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
• The NP-Completeness of Some Edge-Partition Problems
• Planar Formulae and Their Uses
• Approximation algorithms for NP-complete problems on planar graphs
• Genome Rearrangements and Sorting by Reversals

This page was built for publication: Packing triangles in bounded degree graphs.