Bureaucrats, editor, Administrators
373
edits
Changes
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 ..."
== Title ==
Beating 2^n: Faster Exact Algorithms for Some Graph Problems
== Speaker ==
Rajesh Chitnis, University of Maryland
== Abstract ==
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.
Beating 2^n: Faster Exact Algorithms for Some Graph Problems
== Speaker ==
Rajesh Chitnis, University of Maryland
== Abstract ==
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.
