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 coverpartial coverlinear programedge dominating set

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1102774 (Why is no real title available?)
• scientific article; zbMATH DE number 2119674 (Why is no real title available?)
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• A Unified Approach to Approximating Partial Covering Problems
• A linear-time approximation algorithm for the weighted vertex cover problem
• 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
• Minimum Edge Dominating Sets
• Parallel concepts in graph theory
• Paths, Trees, and Flowers

Cited in

(6)

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

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)