Extension of some edge graph problems: standard and parameterized complexity

DOI10.1007/978-3-030-25027-0_13MaRDI QIDQ2291420zbMATH OpenOpenAlexFDO

Authors Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei, Jérôme Monnot, Florian Sikora

Publication date 30 January 2020

Full work available at URL https://basepub.dauphine.fr/handle/123456789/20064

zbMATH Keywords

approximationedge coveredge dominationextension problemsmatchingNP-completenessparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Extension of some edge graph problems: standard, parameterized and approximation complexity
• Approximation hardness of edge dominating set problems
• Algorithms and Computation
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs

Cited in

(13)

• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• The complexity of dependency detection and discovery in relational databases
• On the complexity of solution extension of optimization problems
• Extension and its price for the connected vertex cover problem
• Extension of Vertex Cover and Independent Set in some classes of graphs
• Invited talks
• Parameterized Complexity of Edge Interdiction Problems
• Polynomial-delay and polynomial-space enumeration of large maximal matchings
• Minimal Roman dominating functions: extensions and enumeration
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• On the complexity of some problems related to graph extensions
• Minimal Roman dominating functions: extensions and enumeration
• Polynomial-delay enumeration of large maximal common independent sets in two matroids and beyond

This page was built for publication: Extension of some edge graph problems: standard and parameterized complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2291420)