The robust set problem: parameterized complexity and approximation

DOI10.1007/978-3-642-32589-2_15MaRDI QIDQ2912715zbMATH OpenOpenAlexFDO

Authors Morgan Chopin, Cristina Bazgan

Publication date 25 September 2012

Published in Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32589-2_15

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Parameterized inapproximability of target set selection and generalizations
• Parameterized inapproximability of target set selection and generalizations
• Parameterized approximability of maximizing the spread of influence in networks
• Parameterized approximability of maximizing the spread of influence in networks
• The complexity of finding harmless individuals in social networks

Cited in

(4)

• Seriation in the presence of errors: NP-hardness of \(l_{\infty}\)-fitting Robinson structures to dissimilarity matrices
• The complexity of finding harmless individuals in social networks
• Robustness of PSPACE-complete sets
• Data reductions and combinatorial bounds for improved approximation algorithms

This page was built for publication: The robust set problem: parameterized complexity and approximation

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