Qianping Gu (SFU)
24/01/14 12:30 Talks
Branch-decomposition of graphs and its algorithmic applications
Speaker:
Qianping Gu (Simon Fraser University, Computing Science)
Abstract:
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.
Date:
Friday, January 24, 2014
Time:
12:30 pm - 1:30 pm
Location:
ASB Building, Room No. 9896, Simon Fraser University, Burnaby
Qianping Gu (Simon Fraser University, Computing Science)
Abstract:
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.
Date:
Friday, January 24, 2014
Time:
12:30 pm - 1:30 pm
Location:
ASB Building, Room No. 9896, Simon Fraser University, Burnaby