کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418364 681656 2013 29 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Corner cuts are close to optimal: From solid grids to polygons and back
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Corner cuts are close to optimal: From solid grids to polygons and back
چکیده انگلیسی

We study the solution quality for min-cut problems on graphs when restricting the shapes of the allowed cuts. In particular we are interested in min-cut problems with additional size constraints on the parts being cut out from the graph. Such problems include the bisection problem, the separator problem, or the sparsest cut   problem. We therefore aim at cutting out a given number mm of vertices from a graph using as few edges as possible. We consider this problem on solid grid graphs, which are finite, connected subgraphs of the infinite two-dimensional grid that do not have holes. Our interest is in the tradeoff between the simplicity of the cut shapes and their solution quality: we study corner cuts   in which each cut has at most one right-angled bend. We prove that optimum corner cuts get us arbitrarily close to a cut-out part of size mm, and that this limitation makes us lose only a constant factor in the quality of the solution. We obtain our result by a thorough study of cuts in polygons and the effect of limiting these to corner cuts.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 7–8, May 2013, Pages 970–998
نویسندگان
, , ,