Approximation algorithms and ratios for multiple domination in graphs
We analyse approximation algorithms (greedy heuristics) for the classical domination number and two multiple domination numbers in simple graphs. First, we present a short self-contained proof of the known result that the minimum domination problem in any graph $G$ with maximum degree $Δ$ can be solved within the approximation ratio of ${\ln(Δ+1)+1}$. The proof is based on an analysis of a simple greedy heuristic. Then, by analysing more advanced greedy heuristic techniques and using ideas from our self-contained proof for the classical domination number, we fix a gap in the existing proof…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.22720
curl -X POST /api/v1/records/arxiv/2604.22720/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.22720/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'