Show simple item record

dc.contributor.advisor Dean, Nathaniel
dc.contributor.advisor Cook, William J.
dc.creatorChristian, William Anderson, Jr
dc.date.accessioned 2009-06-04T06:42:54Z
dc.date.available 2009-06-04T06:42:54Z
dc.date.issued 2003
dc.identifier.urihttps://hdl.handle.net/1911/18516
dc.description.abstract We present an algorithmic framework (including a single data structure) that is extended into linear-time algorithms to solve several NP-complete graph problems (i.e., INDEPENDENT SET, M AXIMUM CUT, GRAPH COLORING, HAMILTONIAN CYCLE, and DISJOINT PATHS). The linearity is achieved assuming the provision of a branch decomposition of the instance graph. We then modify the framework to create a multithreaded framework that uses the existing problem-specific extensions without any revision. Computational results for the serial and parallel algorithms are provided. In addition, we present a graphical package called JPAD that can display a graph and branch decomposition, show their relationship to each other, and be extended to rim and display the progress and results of algorithms on graphs or on branch decompositions.
dc.format.extent 108 p.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectMathematics
Industrial engineering
Computer science
dc.title Linear-time algorithms for graphs with bounded branchwidth
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Computer Science
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation Christian, William Anderson, Jr. "Linear-time algorithms for graphs with bounded branchwidth." (2003) Diss., Rice University. https://hdl.handle.net/1911/18516.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record