Approximation algorithms for partially covering with edges

DOI10.1016/j.tcs.2008.02.047zbMath1145.68052OpenAlexW2063671489MaRDI QIDQ930925

Ojas Parekh

Publication date: 24 June 2008

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

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

zbMATH Keywords

approximation algorithmlinear programedge coverpartial coveredge dominating set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Covering problems in edge- and node-weighted graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Parallel concepts in graph theory
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Approximability of the capacitated \(b\)-edge dominating set problem
• Minimum Edge Dominating Sets
• Edge Dominating Sets in Graphs
• A linear-time approximation algorithm for the weighted vertex cover problem
• Algorithms and Computation
• Paths, Trees, and Flowers
• A Unified Approach to Approximating Partial Covering Problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Approximation algorithms for partially covering with edges