Show simple item record

dc.contributor.advisorHicks, Illya V.en_US
dc.creatorWarren, Jeffrey Scotten_US
dc.date.accessioned2010-01-14T23:57:19Zen_US
dc.date.accessioned2010-01-16T01:38:32Z
dc.date.available2010-01-14T23:57:19Zen_US
dc.date.available2010-01-16T01:38:32Z
dc.date.created2007-05en_US
dc.date.issued2009-05-15en_US
dc.identifier.urihttp://hdl.handle.net/1969.1/ETD-TAMU-1332
dc.description.abstractMethods are described that implement a branch-and-price decomposition approach to solve the maximum weight independent set (MWIS) problem. The approach is first described by Warrier et. al, and herein our contributions to this research are presented. The decomposition calls for the exact solution of the MWIS problem on induced subgraphs of the original graph. The focus of our contribution is the use of chordal graphs as the induced subgraphs in this solution framework. Three combinatorial branch-and-bound solvers for the MWIS problem are described. All use weighted clique covers to generate upper bounds, and all branch according to the method of Balas and Yu. One extends and speeds up the method of Babel. A second one modifies a method of Balas and Xue to produce clique covers that share structural similarities with those produced by Babel. Each of these improves on its predecessor. A third solver is a hybrid of the other two. It yields the best known results on some graphs. The related matter of deciding the imperfection or perfection of a graph is also addressed. With the advent of the Strong Perfect Graph Theorem, this problem is reduced to the detection of odd holes and anti-holes or the proof of their absence. Techniques are provided that, for a given graph, find subgraphs in polynomial time that contain odd holes whenever they are present in the given graph. These techniques and some basic structural results on such subgraphs narrow the search for odd holes. Results are reported for the performance of the three new solvers for the MWIS problem that demonstrate that the third, hybrid solver outperforms its clique-cover-based ancestors and, in some cases, the best current open-source solver. The techniques for narrowing the search for odd holes are shown to provide a polynomial-time reduction in the size of the input required to decide the perfection or imperfection of a graph.en_US
dc.format.mediumelectronicen_US
dc.format.mimetypeapplication/pdfen_US
dc.language.isoen_USen_US
dc.subjectindependent seten_US
dc.subjectodd holeen_US
dc.titleIndependent set problems and odd-hole-preserving graph reductionsen_US
dc.typeBooken
dc.typeThesisen
thesis.degree.departmentIndustrial and Systems Engineeringen_US
thesis.degree.disciplineIndustrial Engineeringen_US
thesis.degree.grantorTexas A&M Universityen_US
thesis.degree.nameDoctor of Philosophyen_US
thesis.degree.levelDoctoralen_US
dc.contributor.committeeMemberDeuermeyer, Bryan L.en_US
dc.contributor.committeeMemberHobbs, Arthur M.en_US
dc.contributor.committeeMemberWilhelm, Wilbert E.en_US
dc.type.genreElectronic Dissertationen_US
dc.type.materialtexten_US
dc.format.digitalOriginborn digitalen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record