Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10328704 | Discrete Applied Mathematics | 2005 | 14 Pages |
Abstract
The generalized vertex packing problem seeks to identify a largest subset of nodes from an undirected graph, such that the subgraph induced by this subset of nodes contains no more than some threshold number of edges. This paper derives a class of valid inequalities based on certain special subgraphs called webs, which are general structures that subsume cliques, matchings, odd holes, and odd anti-holes. We also provide a set of conditions for this class of valid inequalities to be facet-inducing for the web subgraph polytope. Finally, we prescribe a web subgraph identification procedure, and test the computational benefits obtained by solving generalized vertex packing instances with formulations augmented by these web-based valid inequalities.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hanif D. Sherali, J. Cole Smith,