Extension of some edge graph problems: standard, parameterized and approximation complexity

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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
The complexity of completing partial Latin squares
Dominating sets for split and bipartite graphs
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
Connected vertex covers in dense graphs
Vertex and edge covers with clustering properties: Complexity and algorithms
Precoloring extension. I: Interval graphs
A special planar satisfiability problem and a consequence of its NP- completeness
The many facets of upper domination
Combinatorial optimization. Polyhedra and efficiency (3 volumes)
Exact algorithms for edge domination
On the complexity of the upper \(r\)-tolerant edge cover problem
Algorithmic aspects of upper edge domination
Efficiently enumerating hitting sets of hypergraphs arising in data profiling
On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
On the complexity of solution extension of optimization problems
Extension of some edge graph problems: standard and parameterized complexity
Tight approximation ratio for Minimum Maximal Matching
Extension of Vertex Cover and Independent Set in some classes of graphs
New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
Approximability of the capacitated \(b\)-edge dominating set problem
Linear time algorithms for generalized edge dominating set problems
On the Complexity Landscape of the Domination Chain
edge dominating set: Efficient Enumeration-Based Exact Algorithms
Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
Edge Dominating Sets in Graphs
On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets
Dual subimplicants of positive Boolean functions
Enumerating Minimal Dominating Sets in Triangle-Free Graphs
Non-approximability results for optimization problems on bounded degree instances
An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
On cliques in graphs
Polynomial-delay and polynomial-space enumeration of large maximal matchings