Improved parameterized algorithms and kernels for mixed domination

DOI10.1016/j.tcs.2020.02.014zbMath1433.68182OpenAlexW3005807565MaRDI QIDQ2310753

Mingyu Xiao, Zimo Sheng

Publication date: 6 April 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.02.014

zbMATH Keywords

graph algorithmsparameterized algorithmskernelizationmixed dominationbranch-and-search

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Unnamed Item ⋮ Upper and lower bounds on approximating weighted mixed domination

Cites Work

• New parameterized algorithms for the edge dominating set problem
• The algorithmic complexity of mixed domination in graphs
• Exact exponential algorithms.
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Mixed Dominating Set: a parameterized perspective
• On the mixed domination problem in graphs
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• An approximation algorithm for the total covering problem
• Total matchings and total coverings of graphs
• Upper and lower bounds on approximating weighted mixed domination
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved parameterized algorithms and kernels for mixed domination