Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.dam.2004.09.008 | Discrete Applied Mathematics |
Keywords | Field | DocType |
odd anti-holes,web graph,web-based valid inequality,largest subset,valid inequality,web subgraph polytope,odd hole,certain special subgraphs,generalized vertex packing,mixed-integer programming,web subgraph identification procedure,web-based facet,generalized vertex packing instance,generalized vertex packing problem,mixed integer programming | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Packing problems,Vertex (graph theory),Polytope,Integer programming,Web application,Mathematics,Graph Node | Journal |
Volume | Issue | ISSN |
146 | 3 | Discrete Applied Mathematics |
Citations | PageRank | References |
2 | 0.37 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hanif D. Sherali | 1 | 3403 | 318.40 |
| J. Cole Smith | 2 | 610 | 43.34 |