The NYU IT team is performing scheduled maintenance on the storage device that supports the Faculty Digital Archive on Wednesday, February 19th starting at 12:30pm EST and continuing though Thursday Februaru 19th. Contents will be available for viewing during this time. However, submitters will not be able to submit or edit items until this maintenance is complete. We apologize for this inconvenience.
| Title: | ALMOST PERFECT MATRICES AND GRAPHS |
| Authors: | Padberg, M. |
| Issue Date: | Oct-1998 |
| Publisher: | Stern School of Business, New York University |
| Series/Report no.: | SOR-99-5 |
| Abstract: | We introduce the notions of w-projection and k-projection that map almost integral polytopes associated with almost perfect graphs G with n nodes from Rn into Rn-w where w is the maximum clique size in G. We show that C. Berge's strong perfect graph conjecture is correct if and only if the projection (of either kind) of such polytopes is again almost integral in Rn-w. Several important properties of w-projections and k-projections are established. We prove that the strong perfect graph conjecture is wrong if an w-projection and a related k-projection of an almost integral polytope with 2 ⤠w ⤠(n - 1)/2 produce different polytopes in Rn-w. |
| URI: | http://hdl.handle.net/2451/14786 |
| Appears in Collections: | IOMS: Statistics Working Papers |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| SOR-99-5.pdf | 705.55 kB | Adobe PDF | View/Open |
Items in FDA are protected by copyright, with all rights reserved, unless otherwise indicated.