Algorithmic Aspects of Upper Domination: A Parameterised Perspective
DOI10.1007/978-3-319-41168-2_10zbMath1476.68114OpenAlexW2488352127MaRDI QIDQ2830063
Kim-Manuel Klein, Mathieu Liedloff, Ljiljana Brankovic, Michael Lampis, Jérôme Monnot, Henning Fernau, Katrin Casel, Vangelis Th. Paschos, Cristina Bazgan, Klaus Jansen
Publication date: 9 November 2016
Published in: Algorithmic Aspects in Information and Management (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-41168-2_10
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (6)
Cites Work
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Exact algorithms for dominating set
- Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
- Improved upper bounds for vertex cover
- On the computational complexity of upper fractional domination
- Data reductions and combinatorial bounds for improved approximation algorithms
- On the parameterized complexity of multiple-interval graph problems
- Pathwidth of cubic graphs and exact algorithms
- On the computational complexity of upper total domination
- The Turing way to parameterized complexity
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- The complexity of irredundant sets parameterized by size
- A Faster Algorithm for Dominating Set Analyzed by the Potential Method
- A Fine-grained Analysis of a Simple Independent Set Algorithm
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Total Domination in Graphs
- Combinatorial bounds via measure and conquer
- Parameterized Algorithms
This page was built for publication: Algorithmic Aspects of Upper Domination: A Parameterised Perspective