The dominating set problem is fixed parameter tractable for graphs of bounded genus
From MaRDI portal
Publication:4815770
DOI10.1016/j.jalgor.2004.02.001zbMath1072.68079OpenAlexW2079313211WikidataQ57360020 ScholiaQ57360020MaRDI QIDQ4815770
No author found.
Publication date: 8 September 2004
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.02.001
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Genus characterizes the complexity of certain graph problems: Some tight results ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Maximum Cut Parameterized by Crossing Number ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ FPT algorithms for domination in sparse graphs and beyond ⋮ Stronger ILPs for the Graph Genus Problem. ⋮ Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor ⋮ Linear time algorithms for finding a dominating set of fixed size in degenerated graphs ⋮ Revising Johnson's table for the 21st century ⋮ A refined search tree technique for dominating set on planar graphs
