The k-restricted 2-factor problem is that of finding a spanning subgraph consisting of disjoint cycles with no cycle of length less than or equal to k. It is a generalization of the well known Hamilton cycle problem and is equivalent to this problem when n2≤k≤n-1 . This paper considers necessary and sufficient conditions, algorithms, and polyhedral conditions for 2-factors in bipartite graphs and restricted 2-factors in bipartite graphs. We introduce a generalization of the necessary and sufficient condition for 4-restricted 2-factors in bipartite graphs to 2k-restricted 2-factors in bipartite graphs of a particular form.
| Identifer | oai:union.ndltd.org:RICE/oai:scholarship.rice.edu:1911/17432 |
| Date | January 2000 |
| Creators | Husband, Summer Michele |
| Contributors | Dean, Nathaniel |
| Source Sets | Rice University |
| Language | English |
| Detected Language | English |
| Type | Thesis, Text |
| Format | 30 p., application/pdf |
Page generated in 0.013 seconds