6 papers
Parameterized String Equations
Laurent Bulteau, Michael R. Fellows, Christian Komusiewicz +1
We study systems of String Equations where block variables need to be assigned strings so that their concatenation gives a specified target string. We investigate this problem unde…
Your Rugby Mates Don't Need to Know your Colleagues: Triadic Closure with Edge Colors
Laurent Bulteau, Niels Grüttemeier, Christian Komusiewicz +1
Given an undirected graph the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edges as \emph{weak} and \emph{strong} such that at most edges a…
Finding a Small Number of Colourful Components
Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin +3
A partition of the vertex set of a graph with a (not necessarily proper) colouring is colourful if no two vertices in any have the same colour and…
Tight Hardness Results for Consensus Problems on Circular Strings and Time Series
Laurent Bulteau, Vincent Froese, Rolf Niedermeier
Consensus problems for strings and sequences appear in numerous application contexts, ranging from bioinformatics over data mining to machine learning. Closing some gaps in the lit…
Consensus Patterns parameterized by input string length is W[1]-hard
Laurent Bulteau
We consider the Consensus Patterns problem, where, given a set of input strings, one is asked to extract a long-enough pattern which appears (with some errors) in all strings. We p…
Precedence-constrained scheduling problems parameterized by partial order width
René van Bevern, Robert Bredereck, Laurent Bulteau +3
Negatively answering a question posed by Mnich and Wiese (Math. Program. 154(1-2):533-562), we show that P2|prec,|, the problem of finding a non-preempti…