Up | ||
Matrix Scaling: A New Heuristic for the Feedback Vertex Set ProblemJames ShookApplied and Computational Mathematics Division, NIST Tuesday, June 10, 2014 15:00-16:00, For a digraph $G$, a set $F\subseteq V(G)$ is said to be a feedback vertex set (FVS) if $G-F$ is acyclic. The problem of finding a smallest FVS is NP-hard. We present a matrix scaling technique for finding feedback vertex sets in un-weighted directed graphs that runs in $O(|F|ln(|V|)|V|^{2})$ time. Our technique seems to produce smaller feedback vertex sets than other known heuristics in a shorter amount of time. Speaker Bio: Dr James Shook obtained a B.S. in Mathematics from the University of Maryland. With the support of a GAANN fellowship he earned a M.S. and Ph.D. in Mathematics from the University of Mississippi. James started in August 2011, as a National Research Council Postdoctoral Research Associate in the Applied and Computational Mathematics Division in the ITL at NIST. Dr. Shook is interested in structural graph theory and the evolution of affiliations in social networks.
Contact: B. Cloteaux Note: Visitors from outside NIST must contact Cathy Graham; (301) 975-3800; at least 24 hours in advance. |