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

Mathematics Subject Classification ID

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)

A survey on enhanced power graphs of finite groups ⋮ Weighted upper domination number ⋮ The many facets of upper domination ⋮ Upper domination: towards a dichotomy through boundary properties ⋮ On the Complexity Landscape of the Domination Chain ⋮ Algorithmic aspects of upper edge domination

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