Packing triangles in low degree graphs and indifference graphs

DOI10.1016/J.DISC.2007.07.100zbMath1136.05073OpenAlexW2132434150MaRDI QIDQ2476287

Gordana Manić, Yoshiko Wakabayashi

Publication date: 18 March 2008

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2007.07.100

zbMATH Keywords

approximation algorithmpolynomial algorithmlow degree graphindifference graphpacking triangles

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (8)

Improved Approximation Algorithms for Weighted 2-Path Partitions ⋮ A polynomial time algorithm for the triangle packing problem on interval graphs ⋮ Improved approximation algorithms for weighted 2-path partitions ⋮ Approximation algorithms and hardness results for the clique packing problem ⋮ MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS ⋮ A Problem Kernelization for Graph Packing ⋮ A randomized approximation algorithm for metric triangle packing ⋮ The parameterized complexity of cycle packing: indifference is not an issue

Cites Work

• Unnamed Item
• Unnamed Item
• Packing subgraphs in a graph
• On approximation properties of the independent set problem for low degree graphs
• Local optimality and its application on independent sets for \(k\)-claw free graphs
• Packing triangles in bounded degree graphs.
• Algorithmic graph theory and perfect graphs
• Optimal greedy algorithms for indifference graphs
• An approximation algorithm for maximum triangle 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
• The NP-Completeness of Some Edge-Partition Problems
• On the Computational Complexity of Combinatorial Problems
• Approximation algorithms for NP-complete problems on planar graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Structural Information and Communication Complexity
• Fundamentals of Computation Theory
• The \(K_r\)-packing problem

This page was built for publication: Packing triangles in low degree graphs and indifference graphs