Approximation hardness of edge dominating set problems
DOI10.1007/S10878-006-7908-0zbMATH Open1255.90121OpenAlexW2592631749MaRDI QIDQ2369972FDOQ2369972
Authors: Miroslav Chlebík, Janka Chlebíková 
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
Recommendations
bounded degree graphsminimum maximal matchingapproximation lower boundeverywhere dense graphsminimum edge dominating set
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)
Cites Work
- Complexity of approximating bounded variants of optimization problems
- Approximation algorithms for NP-complete problems on planar graphs
- Some optimal inapproximability results
- Inapproximability results for bounded variants of optimization problems.
- Edge Dominating Sets in Graphs
- Minimum Edge Dominating Sets
- Title not available (Why is that?)
- Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- The importance of being biased
- Improved non-approximability results for minimum vertex cover with density constraints
- A recognition algorithm for the total graphs
- A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (46)
- Approximating theDomatic Number
- Algorithms – ESA 2004
- Improved approximation bounds for edge dominating set in dense graphs
- Approximability of the capacitated \(b\)-edge dominating set problem
- Approximating the minimum maximal independence number
- Extension of some edge graph problems: standard and parameterized complexity
- Minimum maximal matchings in cubic graphs
- Algorithms and Computation
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- On the hardness of solving edge matching puzzles as SAT or CSP problems
- Upper and lower bounds on approximating weighted mixed domination
- Hardness and approximation of minimum maximal matchings
- Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
- Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
- On approximating (connected) 2-edge dominating set by a tree
- On approximating (connected) 2-edge dominating set by a tree
- Aspects of upper defensive alliances
- Integer programming formulations for the minimum weighted maximal matching problem
- On approximability of the independent/connected edge dominating set problems
- Bounding and approximating minimum maximal matchings in regular graphs
- Title not available (Why is that?)
- Complexity and lowers bounds for power edge set problem
- Complexity and inapproximability results for the power edge set problem
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Approximability of Edge Matching Puzzles
- Algorithmic aspects of upper edge domination
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Decomposition algorithms for solving the minimum weight maximal matching problem
- Algorithms and hardness results for edge total domination problem in graphs
- Approximating edge dominating set in dense graphs
- Tight approximation bounds for dominating set on graphs of bounded arboricity
- Computing and Combinatorics
- Approximation hardness of dominating set problems in bounded degree graphs
- Critical edges for the assignment problem: complexity and exact resolution
- Approximating edge dominating set in dense graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
- Extension of some edge graph problems: standard, parameterized and approximation complexity
- Maximal matching polytope in trees
- Domination versus edge domination
- On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem
- New results on directed edge dominating set
- Title not available (Why is that?)
- A note on approximations of directed edge dominating set
- Mind the gap: edge facility location problems in theory and practice
This page was built for publication: Approximation hardness of edge dominating set problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369972)
