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.
- A Fast Parametric Maximum Flow Algorithm and Applications
- scientific article; zbMATH DE number 56092 (Why is no real title available?)
- scientific article; zbMATH DE number 219924 (Why is no real title available?)
- scientific article; zbMATH DE number 804042 (Why is no real title available?)
- Packing and covering with integral feasible flows in integral supply-demand networks
- Strength and reinforcement of a network and tree packing
- Strength of a graph and packing of trees and branchings
- Testing membership in matroid polyhedra
- On self-complementary cyclic packing of forests
- Main directions in the development of informatics
- Packing algorithms for arborescences (and spanning trees) in capacitated graphs
- An algorithm for packing connectors
- Academician V. S. Mikhalevich as a scientist and science organizer (on the occasion of his 70th birthday)
- An LP-based heuristic algorithm for the node capacitated in-tree packing problem
- Some directions and results of research in mathematical programming and system analysis
- Packing branchings under cardinality constraints on their root sets
- scientific article; zbMATH DE number 4132205 (Why is no real title available?)
- Lagrangian-based column generation for the node capacitated in-tree packing problem
- Packing and covering with integral feasible flows in integral supply-demand networks
- scientific article; zbMATH DE number 19808 (Why is no real title available?)
- Packing Spanning Trees
- A faster algorithm for packing branchings in digraphs
- Packing algorithms for arborescences (and spanning trees) in capacitated graphs
- Integral packing of branchings in capacitaded digraphs
- On cyclic packing of a tree
This page was built for publication: Integral packing of trees and branchings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1907770)
