Show simple item record

dc.contributor.authorMcClosky, Benjamin
dc.date.accessioned 2018-06-19T17:13:02Z
dc.date.available 2018-06-19T17:13:02Z
dc.date.issued 2008-08
dc.identifier.citation McClosky, Benjamin. "Independence Systems and Stable Set Relaxations." (2008) https://hdl.handle.net/1911/102093.
dc.identifier.urihttps://hdl.handle.net/1911/102093
dc.descriptionThis work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/22172
dc.description.abstract Many fundamental combinatorial optimization problems involve the search for subsets of graph elements which satisfy some notion of independence. This thesis develops techniques for optimizing over a class of independence systems and focuses on systems having the vertex set of a finite graph as a ground set. The search for maximum stable sets in a graph offers a well-studied example of such a problem. More generally, for any integer k greater than or equal to one, the maximum co-k-plex problem fits into this framework as well. Co-k-plexes are defined as a relaxation of stable sets. This thesis studies co-k-plexes from polyhedral, algorithmic, and enumerative perspectives. The polyhedral analysis explores the relationship between the stable set polytope and co-k-plex polyhedra. Results include generalizations of odd holes, webs, wheels, and the claw. Sufficient conditions for the integrality of some related linear systems and results on the composition of stable set polyhedra are also given. The algorithmic analysis involves the development of heuristic and exact algorithms for finding maximum k-plexes. This problem is closely related to the search for co-kplexes. The final chapter includes results on the enumerative structure of co-k-plexes in certain graphs.
dc.format.extent 130 pp
dc.title Independence Systems and Stable Set Relaxations
dc.type Technical report
dc.date.note August 2008
dc.type.dcmi Text


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record