UTCS Colloquium/ACT Seminar: Jianer Chen Texas A&M University An O(n%5E4) Time Algorithm for Bounded Feedback Vertex Set ACES 3.408 Friday November 30 2007 10:00 a.m.
Speaker Name/Affiliation: Jianer Chen/Texas A&M University
e: Friday November 30 2007 10:00 a.m.
Location: ACES 3.408
Host: Vijaya Ramachandran
Talk Title: An O(n%5E4) Time Algorithm
for Bounded Feedback Vertex Set
is among the most well-known problems studied in
computer science and in
formation management. A system cannot proceed
when a deadlock occurs. Th
us a set of processes in the system needs to be
rolled back in order to
recover from the deadlock. It is desired that only a small
set of proce
sses is rolled back because process rolling back is expensive.
ally the problem is formulated as the Feedback Vertex Set problem
n a directed graph G remove k vertices from G so that the resulting
ph is acyclic where k is expected to be small). The problem is a well-know
NP-complete problem. An outstanding open problem (mentioned so in more
than 20 published papers in the literature) is whether there is a polyn
time algorithm for the problem if k is a constant.
talk we resolve this open problem and present an O(n%5E4) time
thm for the Feedback Vertex Set problem for any constant k.
a joint work with Y. Liu and S. Lu of Texas A&M University and B.
ullivan and I. Razgon of University College Cork Ireland.
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct