Qianping Gu (SFU)

Branch-decomposition of graphs and its algorithmic applications
Qianping Gu (Simon Fraser University, Computing Science)


The notions of branch-decomposition and branch-width of graphs were introduced by Robertson and Seymour in relation to tree-decomposition and tree-width. The notions play a key role in the graph minor theory and have important algorithmic applications. A graph of small branch-width admits efficient algorithms for a vast class of NP-hard problems on the graph. In this talk, the algorithmic applications of the notions and algorithms for computing branch-decompositions of small width will be introduced.


Friday, January 24, 2014


12:30 pm - 1:30 pm

ASB Building, Room No. 9896, Simon Fraser University, Burnaby