Packing triangles in bounded degree graphs.
From MaRDI portal
Publication:1853132
DOI10.1016/S0020-0190(02)00274-0zbMath1042.68087OpenAlexW1969483202MaRDI QIDQ1853132
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
Related Items
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
