Difference between revisions of "CATS-Feb-7-2014"
From Theory
(Created page with "== Title == Beating 2^n: Faster Exact Algorithms for Some Graph Problems == Speaker == Rajesh Chitnis, University of Maryland == Abstract == Most NP-complete graph problems ...") |
(No difference)
|
Latest revision as of 18:45, 4 February 2014
Title[edit]
Beating 2^n: Faster Exact Algorithms for Some Graph Problems
Speaker[edit]
Rajesh Chitnis, University of Maryland
Abstract[edit]
Most NP-complete graph problems can be solved by brute force in 2^{n} time, where n is the size of the input graph. In this talk, we will describe faster exact algorithms, of the form (2-\epsilon)^n for some constant \epsilon>0, for various problems such as (Directed) Multiway Cut and (Directed) Subset Feedback Vertex Set.
Joint work with Fedor Fomin, Daniel Lokshtanov, Pranabendu Misra, M.S. Ramanujan and Saket Saurabh. Appeared in IPEC '13.
