Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes

DOI10.1145/3154833zbMath1426.68303MaRDI QIDQ4561497

Saket Saurabh, Daniel Lokshtanov, Fedorr V. Fomin

Publication date: 6 December 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3154833

zbMATH Keywords

monadic second-order logic; treewidth; parameterized complexity; polynomial-time approximation scheme; embedded graph; bidimensionality; unit-disk graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

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

68W25: Approximation algorithms

05C62: Graph representations (geometric and intersection representations, etc.)