Refine
Document Type
- ZIB-Report (2)
- Article (1)
Is part of the Bibliography
- no (3)
Keywords
- Covering (1)
- Factors (1)
- Hall's Theorem (1)
- König's Theorem (1)
- Packing (1)
- Total Unimodularity (1)
- balanced hypergraph (1)
- f-factors in hypergraphs (1)
- mengerian hypergraph (1)
- perfect f-matchings in hypergraphs (1)
- perfect hypergraph (1)
Institute
We prove characterizations of the existence of perfect f-matchings in uniform mengerian and perfect hypergraphs. Moreover, we investigate the f-factor problem in balanced hypergraphs. For uniform balanced hypergraphs we prove two existence theorems with purely combinatorial arguments, whereas for non-uniform balanced hypergraphs we show that the f-factor problem is NP-hard.
We state purely combinatorial proofs for König- and Hall-type theorems for a wide class of combinatorial optimization problems. Our methods rely on relaxations of the matching and vertex cover problem and, moreover, on the strong coloring properties admitted by bipartite graphs and their generalizations.
We prove characterizations of the existence of perfect f-matchings in uniform mengerian and perfect hypergraphs. Moreover, we investigate the f-factor problem in balanced hypergraphs. For uniform balanced hypergraphs we prove two existence theorems with purely combinatorial arguments, whereas for non-uniform balanced hypergraphs we show that the f-factor problem is NP-hard.