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

DOI10.1007/BF01758774zbMath0771.05026OpenAlexW2079522169WikidataQ56390661 ScholiaQ56390661MaRDI QIDQ1186784

Herbert H. Westermann, Harold N. Gabow

Publication date: 28 June 1992

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01758774

zbMATH Keywords

algorithmsrigidityframesnetwork flowsgamesforestsShannon switching gamematroid partitioningmatroid sums

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items (39)

A characterisation of the generic rigidity of 2-dimensional point-line frameworks ⋮ Algorithmic problems in right-angled Artin groups: complexity and applications ⋮ Scheduling with interjob communication on parallel processors ⋮ Trees, paths, stars, caterpillars and spiders ⋮ A linear-time algorithm for finding a minimum spanning pseudoforest ⋮ Trees, Paths, Stars, Caterpillars and Spiders ⋮ Cuts, matrix completions and graph rigidity ⋮ Source location with rigidity and tree packing requirements ⋮ An algorithm for two-dimensional rigidity percolation: The pebble game ⋮ Efficient computation of implicit representations of sparse graphs ⋮ Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries ⋮ Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases ⋮ On \(k\)-planar crossing numbers ⋮ Straight-line drawings of 1-planar graphs ⋮ Orientation‐based edge‐colorings and linear arboricity of multigraphs ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Rumor Spreading with No Dependence on Conductance ⋮ Minimize the maximum duty in multi-interface networks ⋮ Efficient algorithms for a mixed k-partition problem of graphs without specifying bases ⋮ Single-pass streaming algorithms to partition graphs into few forests ⋮ The complexity of controlled selection ⋮ A Constructive Arboricity Approximation Scheme ⋮ On the planar split thickness of graphs ⋮ Towards the linear arboricity conjecture ⋮ Rigidity for sticky discs ⋮ A rooted-forest partition with uniform vertex demand ⋮ In search of the densest subgraph ⋮ Combinatorial optimization with interaction costs: complexity and solvable cases ⋮ Unnamed Item ⋮ The Minimum Weight In-Tree Cover Problem ⋮ Parameterized complexity of geometric covering problems having conflicts ⋮ Packing algorithms for arborescences (and spanning trees) in capacitated graphs ⋮ An algorithm for packing connectors ⋮ Random sampling and greedy sparsification for matroid optimization problems ⋮ Sparse hypergraphs and pebble game algorithms ⋮ Minimum Scan Cover with Angular Transition Costs ⋮ Sparsity-certifying graph decompositions ⋮ On some algorithmic aspects of hypergraphic matroids ⋮ On monoid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• A linear-time algorithm for a special case of disjoint set union
• A linear-time algorithm for finding a minimum spanning pseudoforest
• The multi-tree approach to reliability in distributed networks
• The principal minors of a matroid
• Connectivity and edge-disjoint spanning trees
• A data structure for dynamic trees
• On graphs and rigidity of plane skeletal structures
• NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
• Birigidity in the Plane
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Arboricity and Subgraph Listing Algorithms
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• The Algebraic Geometry of Motions of Bar-and-Body Frameworks
• Algorithms for two bottleneck optimization problems
• The Union of Matroids and the Rigidity of Frameworks
• Use of matroid theory in operations research, circuits and systems theory
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• On Generic Rigidity in the Plane
• Network Flow and Testing Graph Connectivity
• BICIRCULAR MATROIDS
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Solution of the Shannon Switching Game
• Minimum partition of a matroid into independent subsets
• Lehmans switching game and a theorem of Tutte and Nash-Williams
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Forests, frames, and games: Algorithms for matroid sums and applications