Multivariate algorithmics for NP-hard string problems

MaRDI QIDQ4967170zbMATH OpenFDO

Authors Laurent Bulteau, Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier

Publication date 3 July 2019

Full work available at URL http://bulletin.eatcs.org/index.php/beatcs/article/view/310/292

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Recommendations

• Reflections on multivariate algorithmics and problem parameterization
• On the parameterised complexity of string morphism problems
• scientific article; zbMATH DE number 2086391
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• On the parameterized intractability of motif search problems

Cited in

(26)

• Foreword: Algorithms, strings and theoretical approaches in the big data era -- special issue in honor of the 60th birthday of Professor Raffaele Giancarlo
• On the kernelization complexity of string problems
• String factorisations with maximum or minimum dimension
• Exact algorithms for the repetition-bounded longest common subsequence problem
• Combinatorial \(n\)-fold integer programming and applications
• Consensus strings with small maximum distance and small distance sum
• Computing equality-free and repetitive string factorisations
• The complexity of binary matrix completion under diameter constraints
• Finding consensus strings with small length difference between input and solution strings
• On the parameterised complexity of string morphism problems
• Reflections on multivariate algorithmics and problem parameterization
• On the parameterised complexity of string morphism problems
• Computing equality-free string factorisations
• The maximum equality-free string factorization problem: gaps vs. no gaps
• Kernelization of Whitney switches
• Consensus strings with small maximum distance and small distance sum
• Separating sets of strings by finding matching patterns is almost always hard
• Combinatorial \(n\)-fold integer programming and applications
• Tight hardness results for consensus problems on circular strings and time series
• On Hardness of Several String Indexing Problems
• Kernelization of Whitney Switches
• Closest substring problems for regular languages
• Polynomial-time equivalences and refined algorithms for longest common subsequence variants
• Backdoor DNFs
• Matrix completion: approximating the minimum diameter
• Binary matrix completion under diameter constraints

This page was built for publication: Multivariate algorithmics for NP-hard string problems

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