کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5128303 1378588 2016 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Progress on the description of identifying code polyhedra for some families of split graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Progress on the description of identifying code polyhedra for some families of split graphs
چکیده انگلیسی

The identifying code problem is a newly emerging search problem, challenging both from a theoretical and a computational point of view, even for special graphs like bipartite graphs and split graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs or to provide bounds for their size.In this work we study the associated polyhedra for some families of split graphs: headless spiders and complete suns. We provide the according linear relaxations, discuss their combinatorial structure, and demonstrate how the associated polyhedra can be entirely described or polyhedral arguments can be applied to find minimum identifying codes for special split graphs. We discuss further lines of research in order to apply similar techniques to obtain strong lower bounds stemming from linear relaxations of the identifying code polyhedron, enhanced by suitable cutting planes to be used in a B&C framework.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 22, Part A, November 2016, Pages 225-240
نویسندگان
, , ,