Exploring Algorithms for Branch Decompositions of Planar Graphs

 
 
 
 

Exploring Algorithms for Branch Decompositions of Planar Graphs

Show simple item record


dc.contributor.advisor Juedes, David en_US
dc.contributor.author Dinh, Hiep en_US
dc.date.accessioned 2009-04-10T09:58:22Z
dc.date.available 2009-04-10T09:58:22Z
dc.date.created 2008 en_US
dc.date.issued 2009-04-10T09:58:22Z
dc.identifier.uri http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1222984625 en_US
dc.identifier.uri http://hdl.handle.net/2374.OX/108423
dc.description 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. en_US
dc.format application/pdf en_US
dc.format 132p. en_US
dc.rights unrestricted en_US
dc.rights Copyright and permissions information available at the source archive en_US
dc.subject branch decompositions en_US
dc.subject parameterized complexity en_US
dc.subject graph decompositions en_US
dc.title Exploring Algorithms for Branch Decompositions of Planar Graphs en_US
dc.type Electronic Thesis or Dissertation en_US
dc.degree.name MS en_US
dc.degree.level masters en_US
dc.degree.discipline Computer Science (Engineering and Technology) en_US
dc.degree.grantor Ohio University en_US
dc.contributor.publisher Ohio University / OhioLINK en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record