[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.

Thank you,

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...
URL: <http://cs-mailman.bu.edu/pipermail/tcs-announce/attachments/20171214/88bac2b0/attachment.html>

More information about the tcs-announce mailing list