Integral packing of trees and branchings
type: Item
instance of: scholarly article
title: Integral packing of trees and branchings
zbMATH Open document ID: 0840.05088
DOI: 10.1007/BF02366792
author: V. A. Trubin
published in: Cybernetics and Systems Analysis
publication date: 1996-03-27T00:00:00Z
review text: We apply the results of our previous publications to propose an \(O(n^2 mp)\) algorithm for the problem of integral packing of spanning trees, where \(n\) and \(m\) respectively are the number of vertices and edges in the graph \(G\) and \(p\) is the time complexity of the maximum flow problem on \(G\). The algorithm constructs a basis solution, so that the optimal solution contains a minimum number of spanning trees of nonzero cardinalities. In other words, the number of nonzero components forming the optimal packing does not exceed \(n\). The proposed algorithm is easily modified for the solution of problems of minimum integral covering of a graph by spanning trees. (\dots) The spanning tree packing problem is transformed into a similar problem for digraphs, specifically, the problem of packing branchings into a given digraph with a distinguished root. A good characterization of this problem is provided by the Edmonds theorem: The maximum cardinality of branchings packed into a digraph is equal to the cardinality of the minimum cut separating the root from any of the vertices. The first strictly polynomial algorithm for the solution of this problem was proposed in [\textit{P. A. Pevzner}, Combinatorial methods in flow problems, Work Collect. 3, Moskva 1979, 113-127 (1979; Zbl 0494.90024)]. However, it has the same shortcomings as the previous algorithms for the undirected case.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 844527
zbMATH Keywords: strictly polynomial algorithms for network strength
zbMATH Keywords: algorithm
zbMATH Keywords: integral packing of spanning trees
zbMATH Keywords: maximum flow
zbMATH Keywords: nonzero components
zbMATH Keywords: minimum integral covering of a graph by spanning trees
zbMATH Keywords: digraph
zbMATH Keywords: branchings
zbMATH Keywords: minimum cut
MaRDI profile type: Publication
cites work: Q4006584
cites work: Q4695811
cites work: Strength and reinforcement of a network and tree packing
cites work: Strength of a graph and packing of trees and branchings
cites work: Q4851330
cites work: Testing membership in matroid polyhedra
cites work: Packing and covering with integral feasible flows in integral supply-demand networks
cites work: A Fast Parametric Maximum Flow Algorithm and Applications
full work available at URL: https://doi.org/10.1007/bf02366792
OpenAlex ID: W2024746969
description: scientific article; zbMATH DE number 844527