کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656719 1632974 2016 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Edge-disjoint odd cycles in 4-edge-connected graphs
ترجمه فارسی عنوان
چرخه های عددی غیر مجزا در گراف های متصل به چهار لبه
کلمات کلیدی
چرخه عجیب، بسته بندی، گرافهای متصل به چهار لبه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Finding edge-disjoint odd cycles is one of the most important problems in graph theory, graph algorithms and combinatorial optimization. One of the difficulties of this problem is that the Erdős–Pósa property does not hold for odd cycles in general. Motivated by this fact, we prove that for any positive integer k  , there exists an integer f(k)f(k) satisfying the following. For any 4-edge-connected graph G=(V,E)G=(V,E), either G has k   edge-disjoint odd cycles or there exists an edge set F⊆EF⊆E with |F|≤f(k)|F|≤f(k) such that G−FG−F is bipartite. We note that the 4-edge-connectivity is best possible in this statement.A similar approach can be applied to an algorithmic question. Suppose that the input graph G is a 4-edge-connected graph with n   vertices. We show that, for any ε>0ε>0, if k=O((log⁡log⁡log⁡n)1/2−ε)k=O((log⁡log⁡log⁡n)1/2−ε), then the k edge-disjoint odd cycle packing problem in G can be solved in polynomial time in n. This result implies the authors' algorithm for the k edge-disjoint paths problem in 4-edge-connected graphs [13].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 119, July 2016, Pages 12–27
نویسندگان
, ,