Sharp separation and applications to exact and parameterized algorithms

DOI10.1007/s00453-011-9555-9zbMath1236.68090WikidataQ60488521 ScholiaQ60488521MaRDI QIDQ2429363

Fedor V. Fomin, Saket Saurabh, Daniel Lokshtanov, Fabrizio Grandoni

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9555-9

zbMATH Keywords

degree constrained spanning tree; separator; exact and parameterized algorithms

Mathematics Subject Classification ID

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

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)