Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs

DOI10.1016/j.dam.2016.06.008zbMath1369.05040arXiv1309.5461OpenAlexW1551836270MaRDI QIDQ2403794

Arijit Ghosh, Arijit Bishnu, Subhabrata Paul

Publication date: 12 September 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.5461

zbMATH Keywords

planar graphskernelizationliar's domination\(k\)-tuple dominationbounded genus graphs\(\mathsf{W}[2\)-hard]

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Algorithmic aspects of paired disjunctive domination in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• A linear kernel for planar red-blue dominating set
• Variations of \(Y\)-dominating functions on graphs
• \(k\)-tuple domination in graphs
• Liar's domination in graphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• Liar's domination in graphs: complexity and algorithm
• A linear time algorithm for liar's domination problem in proper interval graphs
• A refined search tree technique for dominating set on planar graphs
• Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
• Liar's domination
• Polynomial-time data reduction for dominating set
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• Parameterized complexity: exponential speed-up for planar graph problems
• (Meta) Kernelization
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• The Parameterized Complexity of Domination-Type Problems and Application to Linear Codes
• Bidimensionality and Geometric Graphs
• Automata, Languages and Programming

This page was built for publication: Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs