کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328704 | 684868 | 2005 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A class of web-based facets for the generalized vertex packing problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A class of web-based facets for the generalized vertex packing problem A class of web-based facets for the generalized vertex packing problem](/preview/png/10328704.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 146, Issue 3, 15 March 2005, Pages 273-286
Journal: Discrete Applied Mathematics - Volume 146, Issue 3, 15 March 2005, Pages 273-286
نویسندگان
Hanif D. Sherali, J. Cole Smith,