# Forests, frames, and games: Algorithms for matroid sums and applications

@article{Gabow2005ForestsFA, title={Forests, frames, and games: Algorithms for matroid sums and applications}, author={Harold N. Gabow and Herbert H. Westermann}, journal={Algorithmica}, year={2005}, volume={7}, pages={465-497} }

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 intok forests, and finding as many disjoint spanning trees as possible. The notion of a clump in a matroid sum is introduced, and efficient algorithms for clumps are presented. Applications of these algorithms are given to problems arising in the study of the structural rigidity of graphs, the Shannon switching game, and others.

#### Figures and Topics from this paper

#### 82 Citations

A note on packing spanning trees in graphs and bases in matroids

- Mathematics, Computer Science
- Australas. J Comb.
- 2014

We consider the class of graphs for which the edge connectivity is equal to the maximum number of edge-disjoint spanning trees, and the natural generalization to matroids, where the cogirth is equal… Expand

Ranking and ordering problems of spanning trees

- Computer Science, Mathematics
- 2009

This thesis analyzes bispanning graphs with respect to a conjecture due to Mayr and Plaxton that there exists a minimum number of spanning tree with distinct weights required that the weight function fulfills predefined properties and proves this claim for certain subclasses of all weighted bispanting graphs. Expand

Distributed Algorithms as Combinatorial Structures

- Computer Science
- SIGA
- 2015

An overview of both old and recent results that illustrate how finding distributed algorithms as well as proving lower bounds can be reduced to studying combinatorial graph structures. Expand

In Search of the Densest Subgraph

- Computer Science
- Algorithms
- 2019

This survey paper reviews various concepts of graph density, as well as associated theorems and algorithms, and identifies some interesting open problems in the field. Expand

Algorithms for Graph Rigidity and Scene Analysis

- Computer Science, Mathematics
- ESA
- 2003

An efficient algorithm to compute the rigid, redundantly rigid, M-connected, and globally rigid components of a graph using orientations as the main algorithmic tool is given. Expand

Distributed Computing Column 57 Distributed Algorithms as Combinatorial Structures

- Computer Science
- SIGA
- 2015

An overview of both old and recent results that illustrate how finding distributed algorithms as well as proving lower bounds can be reduced to studying combinatorial graph structures. Expand

Fast Algorithms for Pseudoarboricity

- Mathematics, Computer Science
- ALENEX
- 2016

The densest subgraph problem, which asks for a subgraph with the maximum edges-to-vertices ratio d∗, is solvable in polynomial time and it is shown that it can be computed in O(|E| √ log log d ∗) time, and that better estimates can be given for graph classes where d∷ satisfies certain asymptotic bounds. Expand

Edge Disjoint Spanning Trees in an Undirected Graph with E=2(V-1)

- Mathematics, Computer Science
- ArXiv
- 2018

These are the first algorithms to achieve a running time that is a polylog factor from linear, approaching the 1974 linear time algorithm of Robert E. Tarjan for directed graphs. Expand

A rooted-forest partition with uniform vertex demand

- Mathematics, Computer Science
- J. Comb. Optim.
- 2012

It is proved that it is a necessary and sufficient condition for G to contain k edge-disjoint rooted-forests F1,…,Fk with root-sets R1,….,Rk such that each vertex is spanned by exactly d of F1. Expand

A Rooted-Forest Partition with Uniform Vertex Demand

- Mathematics, Computer Science
- WALCOM
- 2010

This paper shall study on a partition of a graph into edge-disjoint rooted-forests such that each vertex is spanned by exactly d components of the partition, where d is a positive integer. Expand

#### References

SHOWING 1-10 OF 42 REFERENCES

Efficient algorithms for matroid sums

- Mathematics
- 1988

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… Expand

A Linear-Time Algorithm for Finding a Minimum Spanning Pseudoforest

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1988

It is shown that a minimum cost spanning pseudoforest of a graph with n vertices and m edges can be found in O(m+n) time, which implies that aminimum spanning tree can be find in O (m) time for graphs with girth at least log(i)n for some constant i. Expand

Efficient Algorithms for Graphic Matroid Intersection and Parity (Extended Abstract)

- Mathematics, Computer Science
- ICALP
- 1985

Improved algorithms for other problems are obtained, including maintaining a minimum spanning tree on a planar graph subject to changing edge costs, and finding shortest pairs of disjoint paths in a network. Expand

A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees

- Mathematics, Computer Science
- Math. Oper. Res.
- 1985

This work considers the problem of finding a set of k edge-disjoint spanning trees in G of minimum total edge cost and presents an implementation of the matroid greedy algorithm that runs in O ( m log m + k 2 n 2 ) time. Expand

Matroid theory and its applications in electric network theory and in statics

- Mathematics
- 1989

I. The topics of this book The concept of a matroid has been known for more than five decades. Whitney (1935) introduced it as a common generalization of graphs and matrices. In the last two decades,… Expand

Maximally Distant Trees and Principal Partition of a Linear Graph

- Mathematics
- 1969

A pair of trees of a graph is said to be maximally distant if the distance between these trees is maximum in the graph. Necessary and sufficient conditions for maximally distant trees are presented.… Expand

NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS

- Mathematics
- 1983

In this paper, we introduce lower-truncated transversal polymatroids, and develop efficient algorithms of network-flow type for those polymatroids. The lower-truncated transversal polymatroid… Expand

Use of matroid theory in operations research, circuits and systems theory

- Mathematics
- 1981

Abstract Recent trends in application of matroid theory to systems problems in operations research and other fields of engineering science are surveyed. Most of the significant applications have been… Expand

Algorithms for Two Bottleneck Optimization Problems

- Mathematics, Computer Science
- J. Algorithms
- 1988

A bottleneck optimization problem on a graph with edge costs is the problem of finding a subgraph of a certain kind that minimizes the maximum edge cost in the subgraph, and a fast algorithms for two bottleneck optimization problems are proposed. Expand

The principal minors of a matroid

- Mathematics
- 1971

Abstract Kishi and Kajitani introduced the concepts of the principal partition of a graph and maximally distant forest pairs . These concepts lead to the determination of the topological degrees of… Expand