[TcsBu] Algorithms and Theory Seminar
Mahendra Varma, Nithin
nvarma at bu.edu
Thu Dec 14 17:40:11 EST 2017
The Algorithms and Theory Seminar will be at 1 pm tomorrow (December 15th) in Room B08 in the MCS building. The speaker for the seminar is Hannah Flynn (BU). Light lunch will be served at 12:45 pm. The title and abstract are appended.
Please take note of the unusual venue.
Title: Fast Parallel Fixed-Parameter Algorithms via Color Coding
Speaker: Hannah Flynn
Abstract: Fixed-parameter algorithms have been successfully applied to solve numerous difficult problems within acceptable time bounds on large inputs. However, most fixed-parameter algorithms are inherently sequential and make little use of the parallel hardware present in modern computers. We show that parallel fixed-parameter algorithms do not only exist for numerous parameterized problems from the literature – including vertex cover, packing problems, finding embeddings, or finding matchings – but that there are parallel algorithms working in time depending only on the parameter (and not on the size of the input) for these problems.
This talk is based on a paper by Max Bannach, Christoph Stockhusen, and Till Tantau (IPEC 2015).
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the tcs-announce