Extension of some edge graph problems: standard and parameterized complexity

DOI10.1007/978-3-030-25027-0_13zbMath1441.68170OpenAlexW2964601315MaRDI QIDQ2291420

Henning Fernau, Katrin Casel, 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

matchingapproximationNP-completenessedge coverparameterized complexityedge dominationextension problems

Mathematics Subject Classification ID

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

Related Items (8)

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 ⋮ Invited talks ⋮ 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

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