The Parameterized Complexity of Finding Point Sets with Hereditary Properties

DOI10.4230/LIPIcs.IPEC.2018.11OpenAlexW2941958622MaRDI QIDQ5009473

Daniel Lokshtanov, David Eppstein

Publication date: 4 August 2021

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

zbMATH Keywords

order typefixed-parameter tractabilityparameterized complexitypoint set pattern matchinglargest pattern-avoiding subset

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Related Items (1)

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of token swapping and its variants
• Ganzzahlige planare Darstellungen der platonischen Körper. (Integral planar representations of the platonic polyhedra)
• A kernelization algorithm for \(d\)-hitting set
• Topologically sweeping an arrangement
• The node-deletion problem for hereditary properties is NP-complete
• Some advances in the no-three-in-line problem
• Parameterized complexity of finding subgraphs with hereditary properties.
• Another disjoint compression algorithm for odd cycle transversal
• Parametrized complexity theory.
• On tree width, bramble size, and expansion
• On the Computational Complexity of Erdős-Szekeres and Related Problems in ℝ3
• Color-coding
• Forbidden Configurations in Discrete Geometry
• Planarity Allowing Few Error Vertices in Linear Time
• Planar Induced Subgraphs of Sparse Graphs
• On the Erdős-Szekeres convex polygon problem
• On a Problem of Heilbronn

This page was built for publication: The Parameterized Complexity of Finding Point Sets with Hereditary Properties