On fractional cut covers

DOI10.1016/j.dam.2019.03.020zbMath1416.05233OpenAlexW2939890945WikidataQ128039142 ScholiaQ128039142MaRDI QIDQ2312658

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

coveringapproximationrandomized algorithmgraph cuts

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)

Uses Software

• CSDP

Cites Work

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