Upper and lower bounds on approximating weighted mixed domination
From MaRDI portal
Publication:5918569
DOI10.1016/j.tcs.2022.10.033OpenAlexW4308357971MaRDI QIDQ5918569
Publication date: 17 November 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2022.10.033
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Parameterized edge dominating set in graphs with degree bounded by 3
- New parameterized algorithms for the edge dominating set problem
- The algorithmic complexity of mixed domination in graphs
- Bibliography on domination in graphs and some basic definitions of domination parameters
- On total covers of graphs
- Approximation algorithms for combinatorial problems
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Mixed Dominating Set: a parameterized perspective
- On the mixed domination problem in graphs
- Improved parameterized algorithms and kernels for mixed domination
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- An approximation algorithm for the total covering problem
- The importance of being biased
- Edge Dominating Sets in Graphs
- Total matchings and total coverings of graphs
- Properties of vertex packing and independence system polyhedra
- Analytical approach to parallel repetition
- Approximation and Online Algorithms
