Approximation hardness of edge dominating set problems

DOI10.1007/s10878-006-7908-0zbMath1255.90121OpenAlexW2592631749MaRDI QIDQ2369972

Janka Chlebíková, Miroslav Chlebík

Publication date: 21 June 2007

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://researchportal.port.ac.uk/portal/en/publications/approximation-hardness-of-edge-dominating-set-problems(2759347d-cc3e-48f6-a6a4-0b943e7fb377).html

zbMATH Keywords

bounded degree graphsminimum maximal matchingapproximation lower boundeverywhere dense graphsminimum edge dominating set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (28)

On approximating (connected) 2-edge dominating set by a tree ⋮ Minimum maximal matchings in cubic graphs ⋮ Hardness and approximation of minimum maximal matchings ⋮ New Results on Directed Edge Dominating Set ⋮ Mind the gap: edge facility location problems in theory and practice ⋮ Domination versus edge domination ⋮ Unnamed Item ⋮ Algorithms and hardness results for edge total domination problem in graphs ⋮ Bounding and approximating minimum maximal matchings in regular graphs ⋮ Approximating Edge Dominating Set in Dense Graphs ⋮ Approximation hardness of dominating set problems in bounded degree graphs ⋮ Integer programming formulations for the minimum weighted maximal matching problem ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Unnamed Item ⋮ Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes ⋮ Unnamed Item ⋮ Aspects of upper defensive alliances ⋮ A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem ⋮ Algorithmic aspects of upper edge domination ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Improved approximation bounds for edge dominating set in dense graphs ⋮ Decomposition algorithms for solving the minimum weight maximal matching problem ⋮ Maximal matching polytope in trees ⋮ Approximating edge dominating set in dense graphs ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems ⋮ On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem ⋮ A note on approximations of directed edge dominating set ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• A 2-approximation algorithm for the minimum weight edge dominating set problem
• Improved non-approximability results for minimum vertex cover with density constraints
• Complexity of approximating bounded variants of optimization problems
• Minimum Edge Dominating Sets
• The importance of being biased
• Edge Dominating Sets in Graphs
• A recognition algorithm for the total graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Some optimal inapproximability results
• Fundamentals of Computation Theory
• A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem

This page was built for publication: Approximation hardness of edge dominating set problems