Directed width parameters: algorithms and structural properties

-
Shiva Kintali, Princeton University
Fine Hall 224

Treewidth of an undirected graph measures how close the graph is to being a tree. Several problems that are NP-hard on general graphs are solvable in polynomial time on graphs with bounded treewidth. Motivated by the success of treewidth, several directed analogues of treewidth have been introduced to measure the similarity of a directed graph to a directed acyclic graph (DAG). Directed treewidth, D-width, DAG-width and Kelly-width are some such width parameters. In this talk, I will present some of the algorithms and structural properties of these parameters with emphasis on Kelly-width and its equivalent characterizations. I will present some recent results and new research directions.