Dynamic parameterized problems
DOI10.1007/S00453-017-0349-6zbMATH Open1393.68074OpenAlexW3003329734MaRDI QIDQ722546FDOQ722546
Authors: R. Krithika, Abhishek Sahu, 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/
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Cites Work
- Turbocharging treewidth heuristics
- Fundamentals of parameterized complexity
- Fixed-parameter tractability of graph modification problems for hereditary properties
- The node-deletion problem for hereditary properties is NP-complete
- Parametrized complexity theory.
- A \(4k^2\) kernel for feedback vertex set
- Incompressibility through Colors and IDs
- On problems as hard as CNF-SAT
- Title not available (Why is that?)
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized algorithms
- On two techniques of combining branching and treewidth
- Incremental list coloring of graphs, parameterized by conservation
- Improved upper bounds for vertex cover
- Graph-Theoretic Concepts in Computer Science
- FPT algorithms for connected feedback vertex set
- Faster deterministic \textsc{Feedback Vertex Set}
- Dynamic dominating set and turbo-charging greedy heuristics
- Vertex cover: Further observations and further improvements
- Parameterized complexity of finding subgraphs with hereditary properties.
- Title not available (Why is that?)
- Feedback vertex set in mixed graphs
- Title not available (Why is that?)
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis
- On the parameterized complexity of dynamic problems
Cited In (19)
- Dynamic Parameterized Problems
- Multistage graph problems on a global budget
- Parametric continuity in dynamic programming problems
- Computing parameters of sequence-based dynamic graphs
- Dynamic Parameterized Problems and Algorithms
- Parameterized Dynamic Cluster Editing
- A generic framework for computing parameters of sequence-based dynamic graphs
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- On the parameterized complexity of dynamic problems with connectivity constraints
- On the parameterized complexity of dynamic problems
- Parameterized dynamic cluster editing
- Dominating sets and connected dominating sets in dynamic graphs
- Dynamic min-max problems
- Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams
- Multistage vertex cover
- Reoptimization of parameterized problems
- Fast dynamic graph algorithms for parameterized problems
- Dynamic parameterized problems and algorithms
- Incremental problems in the parameterized complexity setting
Uses Software
This page was built for publication: Dynamic parameterized problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722546)
