*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 18th October, 2.00 in Fine Hall 224 Speaker: Shiva Kintali (Princeton) Title: Directed width parameters: algorithms and structural properties Abstract : 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. ----------- Next week: Manor Mendel Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)