Integral packing of trees and branchings (Q1907770)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Integral packing of trees and branchings |
scientific article |
Statements
Integral packing of trees and branchings (English)
0 references
27 March 1996
0 references
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.
0 references
strictly polynomial algorithms for network strength
0 references
algorithm
0 references
integral packing of spanning trees
0 references
maximum flow
0 references
nonzero components
0 references
minimum integral covering of a graph by spanning trees
0 references
digraph
0 references
branchings
0 references
minimum cut
0 references