The vertex-disjoint triangles problem

DOI10.1007/10692760_3MaRDI QIDQ4232775zbMATH OpenFDO

Authors C. Pandu Rangan, C. K. Wong, Venkatesan Guruswami, Maw-Shang Chang, Gerard Jennhwa Chang

Publication date 17 August 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/10692760_3

zbMATH Keywords

vertex-disjoint triangles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Packing triangles in low degree graphs and indifference graphs
• Packing triangles in low degree graphs and indifference graphs
• Packing triangles in bounded degree graphs.
• Triangle packing on tripartite graphs is hard
• Independent packings in structured graphs

Cited in

(19)

• On approximating four covering and packing problems
• Treelike comparability graphs
• Improved approximation algorithms for weighted 2-path partitions
• Packing triangles in bounded degree graphs.
• Triangle strings: structures for augmentation of vertex-disjoint triangle sets
• Packing triangles in low degree graphs and indifference graphs
• Independent packings in structured graphs
• On the complexity of colouring antiprismatic graphs
• An improved kernel for planar vertex-disjoint triangle packing
• Improved approximation algorithms for weighted 2-path partitions
• Packing triangles in low degree graphs and indifference graphs
• Triangle packing in (sparse) tournaments: approximation and kernelization
• Triangle packing on tripartite graphs is hard
• 1-Triangle graphs and perfect neighborhood sets
• Graph-Theoretic Concepts in Computer Science
• A randomized approximation algorithm for metric triangle packing
• A polynomial time algorithm for the triangle packing problem on interval graphs
• A deterministic approximation algorithm for metric triangle packing
• An improved approximation algorithm for metric triangle packing

This page was built for publication: The vertex-disjoint triangles problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4232775)