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.
Original language | English (US) |
---|---|
Pages (from-to) | 273-286 |
Number of pages | 14 |
Journal | Discrete Applied Mathematics |
Volume | 146 |
Issue number | 3 |
DOIs | |
State | Published - Mar 15 2005 |
Externally published | Yes |
Keywords
- Generalized vertex packing
- Mixed-integer programming
- Valid inequality
- Web graph
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics