کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646981 | 1342321 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Realizing symmetric set functions as hypergraph cut capacity
ترجمه فارسی عنوان
توابع مجموعه متقارن به عنوان ظرفیت برش هیبرگرا عمل می کنند
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
In this paper, we focus on the case of undirected hypergraphs, which was not dealt with in the previous work of Fujishige and Patkar. For this case, Grishuhin (1989) had given a set of hyperedges forming a basis of the cut realization of symmetric set functions. By using the Möbius inversion formula together with Grishuhin's basis, we extend a result of Fujishige and Patkar for the case of undirected graphs to hypergraphs. We also clarify the kernel of the cut realization, which leads to other interesting bases and an alternative proof of Grishuhin's result. In addition, we provide a new necessary condition for the cut realization by undirected hypergraphs with nonnegative capacity.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 8, 6 August 2016, Pages 2007-2017
Journal: Discrete Mathematics - Volume 339, Issue 8, 6 August 2016, Pages 2007-2017
نویسندگان
Yutaro Yamaguchi,