Covering triangles in edge-weighted graphs

DOI10.1007/S00224-018-9860-7MaRDI QIDQ726109zbMATH OpenOpenAlexWikidataFDO

Authors Zhuo Diao, Zhongzheng Tang, Xujin Chen, Xiaodong Hu

Publication date 3 August 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-018-9860-7

zbMATH Keywords

combinatorial algorithmstriangle packinglinear 3-uniform hypergraphstriangle cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Sufficient conditions for Tuza's conjecture on packing and covering triangles
• Packing triangles in weighted graphs
• Triangle packing and covering in dense random graphs
• On a conjecture of Tuza about packing and covering of triangles
• Total dual integrality of triangle covering

Cites work

• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 1242264 (Why is no real title available?)
• A conjecture on triangles of graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On a Class of Totally Unimodular Matrices
• On a conjecture of Tuza about packing and covering of triangles
• Packing and covering triangles in \(K_{4}\)-free planar graphs
• Packing and covering triangles in graphs
• Packing and covering triangles in planar graphs
• Packing and covering triangles in tripartite graphs
• Packing triangles in weighted graphs
• Sufficient conditions for Tuza's conjecture on packing and covering triangles
• The probabilistic method
• Tuza's conjecture is asymptotically tight for dense graphs

Cited in

(14)

• A sharp upper bound for the transversal number of \(k\)-uniform connected hypergraphs with given size
• scientific article; zbMATH DE number 7764113 (Why is no real title available?)
• On the transversal number of \(k\)-uniform connected hypergraphs
• Packing triangles in weighted graphs
• On the cone of weighted graphs generated by triangles
• Triangle packing and covering in dense random graphs
• Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number
• On the feedback number of 3-uniform linear extremal hypergraphs
• Finding optimal triangulations parameterized by edge clique cover
• Sufficient conditions for Tuza's conjecture on packing and covering triangles
• Total dual integrality of triangle covering
• On the transversal number of rank \(k\) hypergraphs
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Maximal flat antichains of minimum weight

This page was built for publication: Covering triangles in edge-weighted graphs

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