Covering the edges of bipartite graphs using \(K_{2,2}\) graphs

DOI10.1016/J.TCS.2009.08.018zbMath1187.68343OpenAlexW2105245757MaRDI QIDQ1041216

Asaf Levin, Dorit S. Hochbaum

Publication date: 1 December 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.018

zbMATH Keywords

network designapproximation algorithmsset cover

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Unnamed Item ⋮ Unnamed Item ⋮ Structural parameterizations of budgeted graph coloring ⋮ Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization, approximation, and complexity classes
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• A modified greedy heuristic for the set covering problem with improved worst case bound
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• A Greedy Heuristic for the Set-Covering Problem
• The NP-Completeness of Some Edge-Partition Problems
• On Syntactic versus Computational Views of Approximability
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Analysis of Approximation Algorithms for k-Set Cover Using Factor-Revealing Linear Programs

This page was built for publication: Covering the edges of bipartite graphs using \(K_{2,2}\) graphs