Elimination Distance to Bounded Degree on Planar Graphs

DOI10.4230/LIPIcs.MFCS.2020.65OpenAlexW3038423595MaRDI QIDQ5089238

Alexandre Vigny, Sebastian Siebertz, Alexander Lindermayr

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/2007.02413

zbMATH Keywords

parameterized complexitystructural graph theoryelimination distance

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (8)

A Fixed-Parameter Tractable Algorithm for Elimination Distance to Bounded Degree Graphs ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ FPT algorithms to compute the elimination distance to bipartite graphs and more ⋮ Combing a Linkage in an Annulus ⋮ First-order Logic with Connectivity Operators ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ Block elimination distance ⋮ Block elimination distance

Cites Work

• Graph isomorphism parameterized by elimination distance to bounded degree
• Kernelization using structural parameters on sparse graph classes
• Sparsity. Graphs, structures, and algorithms
• Graph minors. V. Excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Fixed-parameter tractable distances to sparse graph classes
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph Minors and Parameterized Algorithm Design
• Rankings of Graphs
• Deciding First-Order Properties of Nowhere Dense Graphs
• A Faster Parameterized Algorithm for Treedepth
• Towards Tight(er) Bounds for the Excluded Grid Theorem
• Parameterized and Exact Computation
• Testing first-order properties for subclasses of sparse graphs
• Parameterized Algorithms
• Elimination distances, blocking sets, and kernels for Vertex Cover

This page was built for publication: Elimination Distance to Bounded Degree on Planar Graphs