[TcsBu] Algorithms and Theory Seminar

Mahendra Varma, Nithin nvarma at bu.edu
Tue Dec 12 12:56:14 EST 2017


Sorry for the late announcement. We will have the last Algorithms and Theory Seminar for this semester on Friday (December 15th). The speaker for the seminar is Hannah Flynn (BU). We will announce the exact time and venue of the talk soon. Appending the title and abstract at the end of the email.

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/20171212/e6755eaf/attachment.html>

More information about the tcs-announce mailing list