Today’s post is about TreeWidth, an awesome concept introduced by Robertson and Seymour, 25 years ago. When I first came across treewidth, I became an instant fan. Definition : A tree-decomposition of a graph is a pair where is a family of subsets of , one for each node of , and is a tree [...]
Archive for January, 2010
Approximating TreeWidth
Posted in algorithms, complexity, graph theory, tagged branch width, cops robber games, courcelle's theorem, path width, tree width on January 28, 2010 | 9 Comments »
Shiva Kintali
Search this Blog
-
-
Top Posts
-
Recent Posts
Categories
- algorithms (10)
- combinatorics (2)
- complexity (18)
- conferences (9)
- graph theory (13)
- mathematics (2)
- polyhedral combinatorics (3)
Archives
- May 2012 (4)
- March 2012 (1)
- February 2012 (1)
- November 2011 (2)
- September 2011 (2)
- July 2011 (1)
- June 2011 (1)
- March 2011 (1)
- February 2011 (1)
- November 2010 (2)
- September 2010 (1)
- July 2010 (1)
- June 2010 (1)
- February 2010 (2)
- January 2010 (1)
- November 2009 (1)
- October 2009 (1)
- September 2009 (3)
- August 2009 (1)
- July 2009 (3)
- June 2009 (3)
- May 2009 (2)
Kintali’s Twitter
- @lreyzin Congratulations. 1 day ago
- New blog post about one of my summer projects. kintali.wordpress.com/2012/05/28/tes… 2 days ago
- Please sign this petition. wwws.whitehouse.gov/petitions/!/pe… 1 week ago
- Please support my new word-building game (Tessel) on Kickstarter. kickstarter.com/projects/10725… 1 week ago
