Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes

DOI10.1145/3154833zbMath1426.68303OpenAlexW2785736399MaRDI QIDQ4561497

Saket Saurabh, Fedorr V. Fomin, Daniel Lokshtanov

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 logictreewidthparameterized complexitypolynomial-time approximation schemeembedded graphbidimensionalityunit-disk graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (4)

A Retrospective on (Meta) Kernelization ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ Bidimensionality and Kernels ⋮ Decomposition of Map Graphs with Applications.

This page was built for publication: Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes