کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420650 | 683966 | 2008 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the stable bb-matching problem in multigraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the stable bb-matching problem in multigraphs On the stable bb-matching problem in multigraphs](/preview/png/420650.png)
چکیده انگلیسی
This paper deals with the stable bb-matching problem in multigraphs, called the stable multiple activities problem, SMA for short. In an SMA instance a multigraph G=(V,E)G=(V,E), capacity b(v)b(v) and a linear order ≺v≺v on the set of edges incident to vv, for each vertex v∈Vv∈V are given. A stable bb-matching is sought, i.e. a set of edges M such that each vertex vv is incident with at most b(v)b(v) edges and for each edge e∉Me∉M a vertex vv incident with ee and b(v)b(v) distinct edges f1,…,fb(v)f1,…,fb(v) incident to vv exist in M , all of them ≺v≺v-smaller than ee.We show how to decrease the computational complexity of the SMA algorithm to run in O(|E|)O(|E|) time and derive some properties of stable bb-matchings.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 5, 1 March 2008, Pages 673–684
Journal: Discrete Applied Mathematics - Volume 156, Issue 5, 1 March 2008, Pages 673–684
نویسندگان
Viera Borbel’ová, Katarína Cechlárová,