Approximation Algorithms for Edge-Covering Problem

DOI10.1007/978-3-540-89985-3_136MaRDI QIDQ3628568zbMATH OpenOpenAlexFDO

Authors Mohammad Hosseinzadeh Moghaddam, Alireza Bagheri

Publication date 20 May 2009

Published in Communications in Computer and Information Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-89985-3_136

zbMATH Keywords

approximation algorithmart galleryedge-coveringedge guardvertex guard

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for partially covering with edges
• An approximation algorithm for the total covering problem
• Approximating vertex cover using edge-based representations
• Approximation algorithms for partial covering problems
• Approximation algorithms for the covering Steiner problem
• An edge-reduction algorithm for the vertex cover problem
• Approximation algorithms for the maximum vertex coverage problem on bounded degree graphs
• Approximation algorithms for the submodular edge cover problem with submodular penalties
• Efficient algorithms for the edge-cover coloring problem
• Approximation algorithm for the multicovering problem

Cites work

• A linear algorithm for computing the visibility polygon from a point
• Approximation algorithms for combinatorial problems
• Introduction to algorithms
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons

Cited in

(10)

• Approximability of Edge Matching Puzzles
• Approximation algorithm for sweep coverage on graph
• Efficient algorithms for the edge-cover coloring problem
• Critical edges for the assignment problem: complexity and exact resolution
• Further NP-hard problems for minimal polygon coverings
• A mixed integer linear program and tabu search approach for the complementary edge covering problem
• Edge covering problem under hybrid uncertain environments
• On approximation algorithm for the edge metric dimension problem
• Computational complexity of the police officer patrol problem on weighted digraphs
• scientific article; zbMATH DE number 2089224 (Why is no real title available?)

This page was built for publication: Approximation Algorithms for Edge-Covering Problem

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