Skip to Main Content
 

Global Search Box

 
 
 
 

ETD Abstract Container

Abstract Header

Exploring Algorithms for Branch Decompositions of Planar Graphs

Abstract Details

2008, Master of Science (MS), Ohio University, Computer Science (Engineering and Technology).

A branch decomposition is a type of graph decomposition closely related to the widely studied tree decompositions introduced by Robertson and Seymour. Unlike tree decompositions, optimal branch decompositions and the branch-width of planar graphs can be computed in polynomial time. The ability to construct optimal branch decompositions in polynomial time leads to efficient solutions for generally hard problems on instances restricted to planar graphs.

This thesis studies efficient algorithms for computing optimal branch decompositions for planar graphs. Our main contribution is an improved software package for graph decompositions with efficient implementations of two additional decomposition classes: carving decompositions and branch decompositions. Polynomial time solutions for Independent-Set on general graphs using path decompositions, tree decompositions, and branch decompositions with bounded width are also explored as examples of how graph decompositions can be used to solve NP-Hard problems.

David Juedes (Advisor)
David Chelberg (Committee Member)
Cynthia Marling (Committee Member)
Xiaoping Shen (Committee Member)
132 p.

Recommended Citations

Citations

  • Dinh, H. (2008). Exploring Algorithms for Branch Decompositions of Planar Graphs [Master's thesis, Ohio University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1222984625

    APA Style (7th edition)

  • Dinh, Hiep. Exploring Algorithms for Branch Decompositions of Planar Graphs. 2008. Ohio University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1222984625.

    MLA Style (8th edition)

  • Dinh, Hiep. "Exploring Algorithms for Branch Decompositions of Planar Graphs." Master's thesis, Ohio University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1222984625

    Chicago Manual of Style (17th edition)