The arboricity of a graph is the minimum number of forests it can be partitioned into. Previous approximation schemes were nonconstructive, i.e., they only approximated the arboricity as a value without computing a corresponding forest partition, as they operate on the related pseudoforest partitions or the dual problem. We propose an algorithm for converting a partition of @math pseudoforests into a partition of @math forests in @math time, where @math is the inverse Ackermann function, when @math expected time is allowed for pre-computation of a perfect hash function. Without perfect hashing, we obtain @math with a data structure by Brodal and Fagerberg that stores graphs of arboricity @math . For every fixed @math , the latter result implies a constructive @math -approximation algorithm with runtime @math by using Kowalik's approximation scheme for pseudoforest partitions. Our algorithm might help in designing a faster exact arboricity algorithm. We also make several remarks on approximation algorithms for the pseudoarboricity and the equivalent graph orientations with smallest maximum indegree, and correct some mistakes made in the literature.
A partition of @math pseudoforests can be converted into a partition of @math forests, and @math if possible, in @math . This is implicit in @cite_16 @cite_9 . (We claim in the appendix in Section that the runtime bound of @math is incorrect.)
@cite_9 @cite_16
2060129302 2159059797
This paper presents improved algorithms for matroid partitioning problems, such as finding a maximum cardinality set of edges of a graph that can be partitioned into k forests. The notion of a clamp in a matroid sum is introduced. Efficient algorithms for problems involving clumps are presented. Applications of these algorithms to problems arising in the study of structural rigidity of graphs, the Shannon switching game and others are given. Matroid theory is the theory of independent sets in a finite universe. The term "independent" is borrowed from linear algebra as is most of the terminology. Many combinatorial problems can be modeled by matroids. A solution is expressed as a maximum cardinality independent set, also referred to as a base, or some other object in matroid theory. This thesis investigates problems that can be modeled with matroid sums. Matroid sums are matroids that can be decomposed into a number of simpler matroids. Typical problems that can be modeled with matroid sums are finding k disjoint spanning trees, the Shannon switching game, finding the arboricity and pseudorarboricity, and problems arising in the study of rigidity of structures. Further problems that can be modeled with matroid sums are the graphic and bicircular packing problem and maximum cardinality bipartite matching. Except for the last the matroid algorithms presented for the above problems yield improved time bounds. This thesis also investigates the theoretical properties of matroid sums. The concept of a clump is introduced. Clumps help to design and analyze algorithms on matroid sums. They lead to the notion of a top clump, which in turn leads to an invariant of a matroid sum and, a fortiori, to a family of invariants of a graph. They generalize another invariant, the principal partition introduced by Kishi and Kajitani and its generalization, the k-minor introduced by Bruno.