Packing triangles in bounded degree graphs.
From MaRDI portal
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 (respectively second) problem is polynomially solvable if the maximum degree of the input graph is at most \(3\) (respectively \(4),\) whereas it is APX-hard for general graphs and NP-hard for planar graphs if the maximum degree is \(4\) (respectively \(5)\) or more.
Recommendations
Cites work
- Approximation algorithms for NP-complete problems on planar graphs
- Complexity and approximation. Combinatorial optimization problems and their approximability properties. Incl. 1 CD-ROM
- Genome Rearrangements and Sorting by Reversals
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 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
- Packing cycles and cuts in undirected graphs
- Planar Formulae and Their Uses
- The NP-Completeness of Some Edge-Partition Problems
Cited in
(41)- On approximating four covering and packing problems
- Triangle packings and 1-factors in oriented graphs
- Brambles and independent packings in chordal graphs
- Packing and covering triangles in graphs
- Restricted assignment scheduling with resource constraints
- Using shortcut edges to maximize the number of triangles in graphs
- Partition into triangles on bounded degree graphs
- Towards optimal kernel for edge-disjoint triangle packing
- Triangle strings: structures for augmentation of vertex-disjoint triangle sets
- Packing \([1, \Delta ]\)-factors in graphs of small degree
- Packing triangles in low degree graphs and indifference graphs
- Independent packings in structured graphs
- Using parametric transformations toward polynomial kernels for packing problems allowing overlaps
- Partition into triangles on bounded degree graphs
- An implicit cover problem in wild population study
- Packing triangles in low degree graphs and indifference graphs
- On Approximating an Implicit Cover Problem in Biology
- The vertex-disjoint triangles problem
- Combinatorial and computational aspects of graph packing and graph decomposition
- Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
- Maximum weight cycle packing in directed graphs, with application to kidney exchange programs
- Triangle packing on tripartite graphs is hard
- Approximation algorithms and hardness results for the clique packing problem
- Approximation algorithms and hardness results for the clique packing problem
- A polynomial time algorithm for the triangle packing problem on interval graphs
- Packing K_rs in bounded degree graphs
- On the complexity of list \(\mathcal{H}\)-packing for sparse graph classes
- Egalitarian roommate allocations: complexity and stability
- Approximation algorithms for non-sequential star packing problems
- On the complexity of list \(\mathcal{H}\)-packing for sparse graph classes
- Packing sets of paths, stars and triangles: tractability and approximability
- Approximation algorithms for the k^+-star packing problem
- Approximation algorithms for non-sequential star packing problems
- Clique factors in pseudorandom graphs
- Directed star packing: tractability, inapproximability, and approximation algorithms
- Hardness and approximation of traffic grooming
- Approximate min-max relations for odd cycles in planar graphs
- Packing and covering triangles 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
This page was built for publication: Packing triangles in bounded degree graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853132)
