Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up

DOI10.1137/S0097539702419649zbMath1114.05072WikidataQ60488760 ScholiaQ60488760MaRDI QIDQ3434987

Fedor V. Fomin, Dimitrios M. Thilikos

Publication date: 3 May 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

graph algorithms; tree-width; graph minors; fixed-parameter algorithm

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

68R10: Graph theory (including graph drawing) in computer science

05C83: Graph minors

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)