Sparsity-certifying graph decompositions

DOI10.1007/S00373-008-0834-4MaRDI QIDQ1043807zbMATH OpenOpenAlexWikidataFDO

Authors Ileana Streinu, Louis Theran

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

zbMATH Keywords

matroidstree decompositionspebble game algorithmsparse graph algorithm

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We describe a new algorithm, the $(k,ell)$-pebble game with colors, and use it obtain a characterization of the family of $(k,ell)$-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special instances of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored pebbles generalize and strengthen the previous results of Lee and Streinu and give a new proof of the Tutte-Nash-Williams characterization of arboricity. We also present a new decomposition that certifies sparsity based on the $(k,ell)$-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms by Gabow, Gabow and Westermann and Hendrickson.

Recommendations

• Pebble game algorithms and \((k,l)\)-sparse graphs
• Pebble game algorithms and sparse graphs
• Sparse hypergraphs and pebble game algorithms
• Algorithms for the d-Dimensional Rigidity Matroid of Sparse Graphs
• Analyzing rigidity with pebble games

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 2188414 (Why is no real title available?)
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• A matroid approach to finding edge connectivity and packing arborescences
• A new proof of Laman's theorem
• Algorithms for graph rigidity and scene analysis
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Characterizing Sparse Graphs by Map Decompositions
• Combinatorial genericity and minimal rigidity
• Conditions for Unique Graph Realizations
• Decomposition of Finite Graphs Into Forests
• Forests, frames, and games: Algorithms for matroid sums and applications
• Minimum partition of a matroid into independent subsets
• On graphs and rigidity of plane skeletal structures
• On the Problem of Decomposing a Graph into n Connected Factors
• Pebble game algorithms and sparse graphs
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• The Union of Matroids and the Rigidity of Frameworks

Cited in

(8)

• Frameworks with forced symmetry. I: Reflections and rotations
• A rooted-forest partition with uniform vertex demand
• Algorithms for detecting dependencies and rigid subsystems for CAD
• Graded sparse graphs and body-length-direction frameworks
• Slider-pinning rigidity: a Maxwell-Laman-type theorem
• Inductive constructions for frameworks on a two-dimensional fixed torus
• Pebble game algorithms and sparse graphs
• Pebble game algorithms and \((k,l)\)-sparse graphs

This page was built for publication: Sparsity-certifying graph decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1043807)