Sparse hypergraphs and pebble game algorithms |
| |
Authors: | Ileana Streinu Louis Theran |
| |
Institution: | aComputer Science Department, Smith College, Northampton, MA 01063, USA;bComputer Science Department, University of Massachusetts, Amherst, MA 01003, USA |
| |
Abstract: | A hypergraph G=(V,E) is (k,ℓ)-sparse if no subset V′ V spans more than k|V′|−ℓ hyperedges. We characterize (k,ℓ)-sparse hypergraphs in terms of graph theoretic, matroidal and algorithmic properties. We extend several well-known theorems of Haas, Lovász, Nash-Williams, Tutte, and White and Whiteley, linking arboricity of graphs to certain counts on the number of edges. We also address the problem of finding lower-dimensional representations of sparse hypergraphs, and identify a critical behavior in terms of the sparsity parameters k and ℓ. Our constructions extend the pebble games of Lee and Streinu A. Lee, I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (8) (2008) 1425–1437] from graphs to hypergraphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|