APPLYING LEHMAN THEOREMS TO PACKING PROBLEMS

Authors
Citation
Fb. Shepherd, APPLYING LEHMAN THEOREMS TO PACKING PROBLEMS, Mathematical programming, 71(3), 1995, pp. 353-367
Citations number
28
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
ISSN journal
0025-5610
Volume
71
Issue
3
Year of publication
1995
Pages
353 - 367
Database
ISI
SICI code
0025-5610(1995)71:3<353:ALTTPP>2.0.ZU;2-7
Abstract
A 0-1 matrix A is ideal if the polyhedron Q(A) = conv{x is an element of Q(V): A . x greater than or equal to 1, x greater than or equal to 0} (V denotes the column index set of A) is integral. Similarly a matr ix is perfect if P(A) = conv{x is an element of Q(V): A . x less than or equal to 1, x greater than or equal to 0} is integral. Little is kn own about the relationship between these two classes of matrices. We c onsider a transformation between the two classes which enables us to a pply Lehman's modified theorem about deletion-minimal nonideal matrice s to obtain new results about packing polyhedra. This results in a pol yhedral description for the stable set polytopes of near-bipartite gra phs (the deletion of any neighbourhood produces a bipartite graph). No te that this class includes the complements of line graphs. To date, t his is the only natural class, besides the perfect graphs, for which s uch a description is known for the graphs and their complements. Some remarks are also made on possible approaches to describing the stable set polyhedra of quasi-line graphs, and more generally claw-free graph s. These results also yield a new class of t-perfect graphs.