Please use this identifier to cite or link to this item:
|Title:||Stronger Bounds And Faster Algorithms For Packing In Generalized Kernel Systems|
|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.|
|Appears in Collections:||Unicamp - Artigos e Outros Documentos|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.