Extension of some edge graph problems: standard, parameterized and approximation complexity
From MaRDI portal
approximationedge coveredge dominationextension problemsmatchingNP-completenessparameterized complexity
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) 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) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cites work
- A special planar satisfiability problem and a consequence of its NP- completeness
- Algorithmic aspects of upper edge domination
- An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Approximability of the capacitated \(b\)-edge dominating set problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Connected vertex covers in dense graphs
- Dominating sets for split and bipartite graphs
- Dual subimplicants of positive Boolean functions
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- Edge Dominating Sets in Graphs
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Enumerating Minimal Dominating Sets in Triangle-Free Graphs
- Exact algorithms for edge domination
- Extension of some edge graph problems: standard and parameterized complexity
- Extension of Vertex Cover and Independent Set in some classes of graphs
- Extensions to minimal synchronizing words
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1104328 (Why is no real title available?)
- scientific article; zbMATH DE number 2090012 (Why is no real title available?)
- Inserting multiple edges into a planar graph
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Linear time algorithms for generalized edge dominating set problems
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Non-approximability results for optimization problems on bounded degree instances
- On cliques in graphs
- On the complexity landscape of the domination chain
- On the complexity of solution extension of optimization problems
- On the complexity of the upper r-tolerant edge cover problem
- On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets
- On the overall and delay complexity of the CLIQUES and Bron-Kerbosch algorithms
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- Polynomial-delay and polynomial-space enumeration of large maximal matchings
- Precoloring extension. I: Interval graphs
- The complexity of completing partial Latin squares
- The many facets of upper domination
- Tight approximation ratio for Minimum Maximal Matching
- Vertex and edge covers with clustering properties: Complexity and algorithms
Cited in
(5)- On residual approximation in solution extension problems
- On the complexity of solution extension of optimization problems
- Extension of some edge graph problems: standard and parameterized complexity
- Extension of Vertex Cover and Independent Set in some classes of graphs
- On the complexity of some problems related to graph extensions
This page was built for publication: Extension of some edge graph problems: standard, parameterized and approximation complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6048430)
