Approximation algorithms for partially covering with edges

DOI10.1016/J.TCS.2008.02.047MaRDI QIDQ930925zbMATH OpenOpenAlexFDO

Authors 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 algorithmedge coveredge dominating setlinear programpartial cover

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2119674
• Computing and Combinatorics
• Approximation algorithms for partial covering problems

Cites work

• A 2-approximation algorithm for the minimum weight edge dominating set problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A Unified Approach to Approximating Partial Covering Problems
• Algorithms and Computation
• Approximability of the capacitated \(b\)-edge dominating set problem
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Edge Dominating Sets in Graphs
• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 2119674 (Why is no real title available?)
• Minimum Edge Dominating Sets
• Parallel concepts in graph theory
• Paths, Trees, and Flowers

Cited in

(6)

• On approximation algorithm for the edge metric dimension problem
• Approximation algorithm for sweep coverage on graph
• Approximability of Edge Matching Puzzles
• Approximation Algorithms for Edge-Covering Problem
• Edge covering problem under hybrid uncertain environments
• scientific article; zbMATH DE number 1754596 (Why is no real title available?)

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

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