Sparsity-certifying graph decompositions
From MaRDI portal
Publication:1043807
DOI10.1007/s00373-008-0834-4zbMath1218.05153arXiv0704.0002OpenAlexW1993757674WikidataQ56651071 ScholiaQ56651071MaRDI QIDQ1043807
Publication date: 9 December 2009
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0704.0002
Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (6)
Algorithms for detecting dependencies and rigid subsystems for CAD ⋮ Slider-pinning rigidity: a Maxwell-Laman-type theorem ⋮ Frameworks with forced symmetry. I: Reflections and rotations ⋮ Graded sparse graphs and body-length-direction frameworks ⋮ A rooted-forest partition with uniform vertex demand ⋮ Inductive constructions for frameworks on a two-dimensional fixed torus
Cites Work
- Unnamed Item
- Unnamed Item
- Rigidity of multi-graphs. I: Linking rigid bodies in n-space
- Forests, frames, and games: Algorithms for matroid sums and applications
- A new proof of Laman's theorem
- An algorithm for two-dimensional rigidity percolation: The pebble game
- A matroid approach to finding edge connectivity and packing arborescences
- Pebble game algorithms and sparse graphs
- On graphs and rigidity of plane skeletal structures
- On the Problem of Decomposing a Graph into n Connected Factors
- Combinatorial genericity and minimal rigidity
- A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
- The Union of Matroids and the Rigidity of Frameworks
- Conditions for Unique Graph Realizations
- Characterizing Sparse Graphs by Map Decompositions
- Minimum partition of a matroid into independent subsets
- Decomposition of Finite Graphs Into Forests
- Algorithms - ESA 2003
This page was built for publication: Sparsity-certifying graph decompositions
