On fractional cut covers

DOI10.1016/J.DAM.2019.03.020MaRDI QIDQ2312658zbMATH OpenOpenAlexWikidataFDO

Authors José Neto, Walid Ben-Ameur

Publication date 17 July 2019

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

Full work available at URL https://doi.org/10.1016/j.dam.2019.03.020

zbMATH Keywords

approximationcoveringgraph cutsrandomized algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Recommendations

• The minimum cut cover problem
• scientific article; zbMATH DE number 4075125
• Covering a graph with cuts of minimum total size
• Fractional covering by cuts
• Fractional covers for forests and matchings

Cites work

• k-Components, Clusters and Slicings in Graphs
• A characterization of weakly bipartite graphs
• A note on a method for generating points uniformly on n -dimensional spheres
• A note on the minimum cut cover of graphs
• An application of graph coloring to printed circuit testing
• An approximability-related parameter on graphs -- properties and applications
• Approximate graph coloring by semidefinite programming
• CSDP, A C library for semidefinite programming
• Cubical coloring -- fractional covering by cuts and semidefinite programming
• Cycle and cocycle coverings of graphs
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Facets of the Bipartite Subgraph Polytope
• Fractional covering by cuts
• Geometric algorithms and combinatorial optimization.
• Geometry of cuts and metrics
• Grothendieck-type inequalities in combinatorial optimization
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3675940 (Why is no real title available?)
• scientific article; zbMATH DE number 2079349 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Minimal cut cover of a graph with an application to the testing of electronic boards
• On the cut polytope
• Paths in graphs
• Randomized metarounding
• Sur le coloriage des graphs
• The biparticity of a graph
• The complexity of determining a shortest cycle of even length
• The ellipsoid method and its consequences in combinatorial optimization
• The fractional chromatic number of mycielski's graphs
• The fractional chromatic number of Zykov products of graphs
• The matroids with the max-flow min-cut property
• The max-cut problem on graphs not contractible to \(K_ 5\)
• The maximum cut problem
• Tight approximation algorithms for maximum general assignment problems
• Weakly bipartite graphs and the max-cut problem

Cited in

(4)

• The minimum cut cover problem
• A Sharp Bound on the Ratio Between Optimal Integer and Fractional Covers
• Fractional covering by cuts
• A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem

Describes a project that uses

Uses Software

• CSDP

This page was built for publication: On fractional cut covers

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