Lower bounds for protrusion replacement by counting equivalence classes

DOI10.1016/j.dam.2019.02.024zbMath1437.05224OpenAlexW2963511265WikidataQ128267947 ScholiaQ128267947MaRDI QIDQ2174552

Bart M. P. Jansen, Jules Wulms

Publication date: 21 April 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/6927/

zbMATH Keywords

independent setequivalence classesfinite integer indexboundaried graphsprotrusions

Mathematics Subject Classification ID

Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ The Effect of Planarization on Width

Cites Work

• Unnamed Item
• Unnamed Item
• Kernelization using structural parameters on sparse graph classes
• Mixed searching and proper-path-width
• Some simplified NP-complete graph problems
• Reduction algorithms for graphs of small treewidth
• Planar graphs, via well-orderly maps and trees
• Hitting Forbidden Minors: Approximation and Kernelization
• (Meta) Kernelization
• Vertex Cover Structural Parameterization Revisited
• Explicit Linear Kernels via Dynamic Programming
• The Effect of Planarization on Width
• The Effect of Planarization on Width
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Parameterized Algorithms

This page was built for publication: Lower bounds for protrusion replacement by counting equivalence classes