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 algorithmslinear 3-uniform hypergraphstriangle covertriangle packing

Mathematics Subject Classification ID

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

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

• A conjecture on triangles of graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• scientific article; zbMATH DE number 43754 (Why is no real title available?)
• scientific article; zbMATH DE number 1242264 (Why is no real title available?)
• 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)

• Maximal flat antichains of minimum weight
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal
• Triangle packing and covering in dense random graphs
• Characterizing 3-uniform linear extremal hypergraphs on feedback vertex number
• A sharp upper bound for the transversal number of k-uniform connected hypergraphs with given size
• 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
• Packing triangles in weighted graphs
• On the cone of weighted graphs generated by triangles
• scientific article; zbMATH DE number 7764113 (Why is no real title available?)
• On the transversal number of rank k hypergraphs
• On the transversal number of k-uniform connected hypergraphs

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)