کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141894 957100 2007 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Generalizing the induced matching by edge capacity constraints
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
Generalizing the induced matching by edge capacity constraints
چکیده انگلیسی

Given an edge-weighted graph, the induced matching problem is an edge packing problem, which asks to find a maximum weight edge set such that every edge in the graph is adjacent to at most one edge in the set. In this paper, we generalize this problem by introducing edge capacities and propose an approximation algorithm to the problem. The analysis of this algorithm is based on a relationship between two polytopes for an LP relaxation of the above problem and the capacitated bb-matching problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 4, Issue 2, 1 June 2007, Pages 198–205
نویسندگان
, ,