An approximation algorithm for the total covering problem

DOI10.7151/DMGT.1380MaRDI QIDQ3504806zbMATH OpenOpenAlexFDO

Authors Pooya Hatami

Publication date 18 June 2008

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1008.3216

zbMATH Keywords

approximation algorithmcoveringtotal covering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We introduce a $2$-approximation algorithm for the minimum total covering number problem.

Cited in

(25)

• Universal approximations for TSP, Steiner tree, and set cover
• On the complexity of variations of mixed domination on graphs
• scientific article; zbMATH DE number 1754596 (Why is no real title available?)
• A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem
• scientific article; zbMATH DE number 7758359 (Why is no real title available?)
• scientific article; zbMATH DE number 2000148 (Why is no real title available?)
• Improved parameterized algorithms and kernels for mixed domination
• Upper and lower bounds on approximating weighted mixed domination
• Mixed domination and 2-independence in trees
• Approximation Algorithms for Barrier Sweep Coverage
• A new approximation algorithm for k-set cover problem
• One for the price of two: a unified approach for approximating covering problems
• An exact algorithm for the maximal covering problem
• scientific article; zbMATH DE number 7764100 (Why is no real title available?)
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Approximating the Minimum Tour Cover with a Compact Linear Program
• Approximation Algorithms for Edge-Covering Problem
• Approximation algorithm for sweep coverage on graph
• Efficient algorithms for the conditional covering problem
• Approximation Algorithms for the k-Clique Covering Problem
• Mixed Roman domination in graphs
• Tight approximation bounds for combinatorial frugal coverage algorithms
• A greedy algorithm to construct covering arrays using a graph representation
• Approximation algorithms for some minimum postmen cover problems
• An optimal algorithm for the minimum disc cover problem

This page was built for publication: An approximation algorithm for the total covering problem

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