Dynamic parameterized problems

DOI10.1007/S00453-017-0349-6zbMath1393.68074OpenAlexW3003329734MaRDI QIDQ722546

Abhishek Sahu, R. Krithika, Prafullkumar Tale

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

dynamic problemsfixed-parameter tractabilitykernelization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Multistage graph problems on a global budget ⋮ Multistage vertex cover ⋮ Reoptimization of parameterized problems ⋮ Parameterized dynamic cluster editing ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Parameterized Dynamic Cluster Editing

Uses Software

• tw-heuristic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Incremental list coloring of graphs, parameterized by conservation
• FPT algorithms for connected feedback vertex set
• Improved upper bounds for vertex cover
• On the parameterized complexity of dynamic problems
• On two techniques of combining branching and treewidth
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized complexity of finding subgraphs with hereditary properties.
• Faster deterministic \textsc{Feedback Vertex Set}
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Parametrized complexity theory.
• Vertex Cover: Further Observations and Further Improvements
• A 4 k ² kernel for feedback vertex set
• Turbo-Charging Dominating Set with an FPT Subroutine: Further Improvements and Experimental Analysis
• Incompressibility through Colors and IDs
• On Problems as Hard as CNF-SAT
• Feedback Vertex Set in Mixed Graphs
• Exact Algorithms via Monotone Local Search
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Dynamic parameterized problems