Packing triangles in bounded degree graphs.

DOI10.1016/S0020-0190(02)00274-0zbMath1042.68087MaRDI 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-hardness; Polynomial algorithm; APX-hardness; Planar graphs; Packing triangles

Mathematics Subject Classification ID

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

Related Items

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

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