Approximation hardness of edge dominating set problems
From MaRDI portal
Publication:2369972
Recommendations
Cites work
- scientific article; zbMATH DE number 3674114 (Why is no real title available?)
- scientific article; zbMATH DE number 2011853 (Why is no real title available?)
- scientific article; zbMATH DE number 2119674 (Why is no real title available?)
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
- A recognition algorithm for the total graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Complexity of approximating bounded variants of optimization problems
- Edge Dominating Sets in Graphs
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Improved non-approximability results for minimum vertex cover with density constraints
- Inapproximability results for bounded variants of optimization problems.
- Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
- Minimum Edge Dominating Sets
- Some optimal inapproximability results
- The importance of being biased
Cited in
(46)- On approximability of the independent/connected edge dominating set problems
- Approximability of the capacitated \(b\)-edge dominating set problem
- A note on approximations of directed edge dominating set
- On approximating (connected) 2-edge dominating set by a tree
- Approximating the minimum maximal independence number
- Bounding and approximating minimum maximal matchings in regular graphs
- On approximating (connected) 2-edge dominating set by a tree
- Aspects of upper defensive alliances
- Algorithmic aspects of upper edge domination
- Approximating edge dominating set in dense graphs
- Computing and Combinatorics
- On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem
- Hardness and approximation of minimum maximal matchings
- Approximating edge dominating set in dense graphs
- Approximation hardness of dominating set problems in bounded degree graphs
- 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
- Domination versus edge domination
- On the hardness of solving edge matching puzzles as SAT or CSP problems
- Extension of some edge graph problems: standard, parameterized and approximation complexity
- Extension of some edge graph problems: standard and parameterized complexity
- Critical edges for the assignment problem: complexity and exact resolution
- Approximating theDomatic Number
- Complexity and lowers bounds for power edge set problem
- Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
- scientific article; zbMATH DE number 2080196 (Why is no real title available?)
- Decomposition algorithms for solving the minimum weight maximal matching problem
- scientific article; zbMATH DE number 7650074 (Why is no real title available?)
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Integer programming formulations for the minimum weighted maximal matching problem
- Tight approximation bounds for dominating set on graphs of bounded arboricity
- Algorithms and hardness results for edge total domination problem in graphs
- Minimum maximal matchings in cubic graphs
- On kernelization for edge dominating set under structural parameters
- Approximability of Edge Matching Puzzles
- Complexity and inapproximability results for the power edge set problem
- Max-min greedy matching
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Upper and lower bounds on approximating weighted mixed domination
- Algorithms – ESA 2004
- New results on directed edge dominating set
- Algorithms and Computation
- Mind the gap: edge facility location problems in theory and practice
- Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- Maximal matching polytope in trees
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)
