Algorithmic aspects of upper edge domination
type: Item
instance of: scholarly article
title: Algorithmic aspects of upper edge domination
author: Jérôme Monnot
author: Henning Fernau
author: David F. Manlove
published in: Theoretical Computer Science
publication date: 2021-06-23T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7362197
zbMATH Keywords: edge dominating set
zbMATH Keywords: \( \mathsf{NP} \)-completeness
zbMATH Keywords: approximability
MaRDI profile type: Publication
full work available at URL: j.tcs.2021.03.038
OpenAlex ID: W3147336403
cites work: A Dichotomy for Upper Domination in Monogenic Classes
cites work: A Boundary Property for Upper Domination
cites work: Upper domination: towards a dichotomy through boundary properties
cites work: Some APX-completeness results for cubic graphs
cites work: Q4258216
cites work: Domination chain: characterisation, classical complexity, parameterised complexity and approximability
cites work: Algorithmic Aspects of Upper Domination: A Parameterised Perspective
cites work: Upper Domination: Complexity and Approximation
cites work: The many facets of upper domination
cites work: On the computational complexity of upper fractional domination
cites work: Approximation hardness of edge dominating set problems
cites work: Complexity of approximating bounded variants of optimization problems
cites work: Contributions to the theory of domination, independence and irredundance in graphs
cites work: Paths, Trees, and Flowers
cites work: New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
cites work: The Private Neighbor Cube
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
cites work: On the complexity of the upper \(r\)-tolerant edge cover problem
cites work: Q4368729
cites work: Q4368728
cites work: Minimum Edge Dominating Sets
cites work: Chordal graphs and upper irredundance, upper domination and independence
cites work: Approximation algorithms for combinatorial problems
cites work: Weighted upper edge cover: complexity and approximability
cites work: Weighted Upper Edge Cover: Complexity and Approximability
cites work: NP-completeness of some type of p-center problem
cites work: An Analysis of the Greedy Heuristic for Independence Systems
cites work: Optimization, approximation, and complexity classes
cites work: Q4527015
cites work: Approximating edge dominating set in dense graphs
cites work: Non-approximability results for optimization problems on bounded degree instances
cites work: Edge Dominating Sets in Graphs
cites work: Q3002782
DOI: 10.1016/J.TCS.2021.03.038
Recommended article: Algorithmic aspects of upper paired-domination in graphs
Recommended article: Exact algorithms for edge domination
Recommended article: Exact Algorithms for Edge Domination
Recommended article: Algorithmic Aspects of Upper Domination: A Parameterised Perspective
Recommended article: Q4247463
Recommended article: On the algorithmic complexity of edge total domination
Recommended article: Upper Domination: Complexity and Approximation
Recommended article: Algorithmic Aspects of Some Variants of Domination in Graphs
Recommended article: On the computational complexity of upper total domination
Recommended article: Total vertex-edge domination in graphs: Complexity and algorithms
description: scientific article; zbMATH DE number 7362197