Reoptimization of parameterized problems

DOI10.1007/S00236-022-00428-YMaRDI QIDQ2170282zbMATH OpenOpenAlexFDO

Authors Hans-Joachim Böckenhauer, Elisabet Burjons, Martin Raszyk, Peter Rossmanith

Publication date 30 August 2022

Published in Acta Informatica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

treewidthparameterised complexityvertex-covercrown decompositioncoNP/polyreoptimisation

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• On the parameterized complexity of dynamic problems
• On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
• Reoptimization of Weighted Graph and Covering Problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A 2k-kernelization algorithm for vertex cover based on crown decomposition
• A \(2k\)-vertex kernel for maximum internal spanning tree
• A completeness theory for polynomial (Turing) kernelization
• A linear vertex kernel for maximum internal spanning tree
• A theory and algorithms for combinatorial reoptimization
• Crown structures for vertex cover kernelization
• Deterministic parameterized connected vertex cover
• Dynamic parameterized problems
• Dynamic parameterized problems and algorithms
• Finding odd cycle transversals.
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fundamentals of parameterized complexity
• Introduction to algorithms.
• Kernel bounds for disjoint cycles and disjoint paths
• Kernel(s) for problems with no kernel
• Kernelization lower bounds through colors and IDs
• On finding directed trees with many leaves
• On problems without polynomial kernels
• On the Hardness of Reoptimization
• On the parameterized complexity of dynamic problems
• Parameterized algorithms
• Parametrized complexity theory.
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Reoptimizing the traveling salesman problem
• Scheduling with forbidden sets
• Spanning trees: A survey
• Vertex packings: Structural properties and algorithms

Cited in

(3)

• On the Hardness of Reoptimization with Multiple Given Solutions
• On the existence of polynomial-time approximation schemes for the reoptimization of discrete optimization problems
• Reoptimization of NP-Hard Problems

This page was built for publication: Reoptimization of parameterized problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170282)