کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949948 | 1440207 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Packing non-zero A-paths via matroid matching
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A Î-labeled graph is a directed graph G in which each edge is associated with an element of a group Î by a label function Ï:E(G)âÎ. For a vertex subset AâV(G), a path (in the underlying undirected graph) is called an A-path if its start and end vertices belong to A and does not intersect A in between, and an A-path is called non-zero if the ordered product of the labels along the path is not equal to the identity of Î. Chudnovsky et al. (2006) introduced the problem of packing non-zero A-paths and gave a min-max formula for characterizing the maximum number of vertex-disjoint non-zero A-paths. In this paper, we show that the problem of packing non-zero A-paths can be reduced to the matroid matching problem on a certain combinatorial matroid, and discuss how to derive the min-max formula based on Lovász' idea of reducing Mader's S-paths problem to matroid matching.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 214, 11 December 2016, Pages 169-178
Journal: Discrete Applied Mathematics - Volume 214, 11 December 2016, Pages 169-178
نویسندگان
Shin-ichi Tanigawa, Yutaro Yamaguchi,