Incremental problems in the parameterized complexity setting

DOI10.1007/S00224-016-9729-6MaRDI QIDQ519883zbMATH OpenOpenAlexFDO

Authors Bernard Mans, Luke Mathieson

Publication date 31 March 2017

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-016-9729-6

zbMATH Keywords

parameterized complexitykernelizationtractabilityincremental computationalgorithm complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Complexity models for incremental computation
• scientific article; zbMATH DE number 512869
• Dynamic parameterized problems
• On the computational complexity of dynamic graph problems
• Parameterized dynamic cluster editing

Cites work

• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Applying modular decomposition to parameterized cluster editing problems
• Complexity models for incremental computation
• Dynamic complexity theory revisited
• Fast algorithms for determining (generalized) core groups in social networks
• On the computational complexity of dynamic graph problems
• On the parameterised complexity of string morphism problems
• Optimal decremental connectivity in planar graphs
• Parameterized complexity of Vertex Cover variants
• Parametrized complexity theory.
• The parameterized complexity of editing graphs for bounded degeneracy
• Topology-oriented incremental computation of Voronoi diagrams of circular arcs and straight-line segments

Cited in

(3)

• An Incremental Model for Combinatorial Maximization Problems
• Introduction to reconfiguration
• Bounded incremental computation

This page was built for publication: Incremental problems in the parameterized complexity setting

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