Algorithmic aspects of upper edge domination
From MaRDI portal
Publication:2034795
DOI10.1016/j.tcs.2021.03.038OpenAlexW3147336403MaRDI QIDQ2034795
Henning Fernau, Jérôme Monnot, David F. Manlove
Publication date: 23 June 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.03.038
Related Items
In memory of Jérôme Monnot, Extension of some edge graph problems: standard, parameterized and approximation complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Upper domination: towards a dichotomy through boundary properties
- On the computational complexity of upper fractional domination
- Approximating edge dominating set in dense graphs
- NP-completeness of some type of p-center problem
- Contributions to the theory of domination, independence and irredundance in graphs
- Chordal graphs and upper irredundance, upper domination and independence
- Optimization, approximation, and complexity classes
- Approximation algorithms for combinatorial problems
- Some simplified NP-complete graph problems
- Some APX-completeness results for cubic graphs
- The many facets of upper domination
- On the complexity of the upper \(r\)-tolerant edge cover problem
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Weighted upper edge cover: complexity and approximability
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Complexity of approximating bounded variants of optimization problems
- Approximation hardness of edge dominating set problems
- A Boundary Property for Upper Domination
- Upper Domination: Complexity and Approximation
- Algorithmic Aspects of Upper Domination: A Parameterised Perspective
- A Dichotomy for Upper Domination in Monogenic Classes
- Minimum Edge Dominating Sets
- Edge Dominating Sets in Graphs
- An Analysis of the Greedy Heuristic for Independence Systems
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The Private Neighbor Cube
- Non-approximability results for optimization problems on bounded degree instances
- Weighted Upper Edge Cover: Complexity and Approximability
- Paths, Trees, and Flowers
