Please use this identifier to cite or link to this item:
Type: Artigo
Title: Stronger Bounds And Faster Algorithms For Packing In Generalized Kernel Systems
Author: Leston-Rey
Mario; Lee
Abstract: In this paper, we consider integral (and fractional) packing problems in generalized kernel systems with a mixed family (gksmf). This framework generalizes combinatorial packing problems of several structures as, for instance, st-flows, arborescences, kernel systems, branchings, convex branchings, and covers in bi-set systems. We provide an algorithm, which improves by a factor of 2 on the upperbound for the size of a packing in a gksmf, provided by Leston-Rey and Wakabayashi. This in turn implies the following upperbounds, where n is the number of vertices, m the number of arcs, and r the number of root-sets of a digraph: m for the size of a packing of st-paths; for the size of a packing of spanning arborescences; for the size of a packing of spanning branchings; for the size of a packing of Fujishige's convex branchings; m for the size of a packing of dijoins of a restricted form; and for the size of a packing in Frank's bi-set systems with the mixed intersection property. Next, we consider the framework of uncrossing gksmf. We describe an algorithm for computing a packing in such a framework with the same upperbound guarantee. The time complexity of this algorithm implies an improvement over the best time complexity bounds known for computing a packing of spanning arborescences of Gabow and Manu, for computing a packing of spanning branchings of Lee and Leston-Rey, and for computing a packing of covers in a bi-set system with the mixed intersection property of B,rczi and Frank.
Subject: Arborescence
Editor: Springer Heidelberg
Rights: fechado
Identifier DOI: 10.1007/s10107-015-0948-4
Date Issue: 2016
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
000382053900002.pdf821.16 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.