An approximation algorithm for maximum triangle packing
From MaRDI portal
Publication:2492197
DOI10.1016/j.dam.2005.11.003zbMath1101.68983OpenAlexW2129303870MaRDI QIDQ2492197
Shlomi Rubinstein, Refael Hassin
Publication date: 9 June 2006
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2005.11.003
Analysis of algorithms (68W40) Approximation algorithms (68W25) Randomized algorithms (68W20) Combinatorial aspects of packing and covering (05B40)
Related Items
Improved Approximation Algorithms for Weighted 2-Path Partitions, A parameterized perspective on packing paths of length two, Local improvement algorithms for a path packing problem: a performance analysis based on linear programming, Matching and weighted \(P_2\)-packing: algorithms and kernels, On the parameterized complexity of compact set packing, Improved approximation algorithms for weighted 2-path partitions, Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems, Triangle strings: structures for augmentation of vertex-disjoint triangle sets, Computing the differential of a graph: hardness, approximability and exact algorithms, Improved Algorithms for Several Parameterized Problems Based on Random Methods, Approximation results for the weighted \(P_4\) partition problem, The path partition problem and related problems in bipartite graphs, Packing triangles in low degree graphs and indifference graphs, On linear and semidefinite programming relaxations for hypergraph matching, MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS, A randomized approximation algorithm for metric triangle packing, A local search algorithm for binary maximum 2-path partitioning, An improved randomized approximation algorithm for maximum triangle packing, Induced packing of odd cycles in planar graphs, A Parameterized Perspective on Packing Paths of Length Two, Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An approximation algorithm for maximum packing of 3-edge paths
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Better approximations for max TSP
- Greedy Local Improvement and Weighted Set Packing Approximation
- On Local Search for Weighted k-Set Packing
- 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
- `` Strong NP-Completeness Results
- A Staged Primal-Dual Algorithm for Finding a Minimum Cost Perfect Two-Matching in an Undirected Graph
- Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
