Packing in generalized kernel systems: a framework that generalizes packing of branchings

DOI10.1007/S10107-014-0746-4MaRDI QIDQ2515040zbMATH OpenOpenAlexFDO

Authors Mario Leston-Rey, Yoshiko Wakabayashi

Publication date 9 February 2015

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-014-0746-4

zbMATH Keywords

arborescencebranchinglaminaritypacking

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Review text

This article studies packing problems in the context of the generalized kernel system framework. The authors begin with an introduction to kernels and kernel systems and provide an overview of the literature and the necessary background definitions. The important properties of kernel systems and examples are then presented in the second section. In the third section, the authors present a generalization of the existing algorithms which is further expanded in the fourth section with the introduction of the notion of a mixed family. The use of the framework in packing problems is studied in the fifth section. The sixth section introduces an additional axiom which produces a new framework of uncrossing generalized kernel systems for which a large number of useful theorems and properties are presented with proof, including their applicability for packing problems.

Recommendations

• Stronger bounds and faster algorithms for packing in generalized kernel systems
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• A faster algorithm for packing branchings in digraphs
• Integral packing of branchings in capacitaded digraphs
• Packing branchings under cardinality constraints on their root sets

Cites work

• A note on disjoint arborescences
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connections in combinatorial optimization
• Directed cut transversal packing for source-sink connected graphs
• Fractional packing in ideal clutters
• Fractional Packing ofT-Joins
• scientific article; zbMATH DE number 5764894 (Why is no real title available?)
• scientific article; zbMATH DE number 3661345 (Why is no real title available?)
• Increasing the rooted connectivity of a digraph by one
• Min-max Relations for Directed Graphs
• On covering intersecting set-systems by digraphs
• On two minimax theorems in graph
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Packing arborescences
• Variations for Lovász’ Submodular Ideas

Cited in

(3)

• Packing branchings under cardinality constraints on their root sets
• Stronger bounds and faster algorithms for packing in generalized kernel systems
• A faster algorithm for packing branchings in digraphs

This page was built for publication: Packing in generalized kernel systems: a framework that generalizes packing of branchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2515040)