A Combinatorial Proof of a König-type Theorem for Unimodular Hypergraphs
Please always quote using this URN: urn:nbn:de:0297-zib-64017
under review
- 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.
Download full text files
Additional Services
| Author: | Isabel BeckenbachORCiD, Britta Peis, Oliver Schaudt, Robert Scheidweiler |
|---|---|
| Document Type: | ZIB-Report |
| Tag: | Covering; Factors; König's Theorem; Packing; Total Unimodularity |
| MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C65 Hypergraphs |
| 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C70 Factorization, matching, partitioning, covering and packing | |
| Date of first Publication: | 2017/05/16 |
| Series (Serial Number): | ZIB-Report (17-27) |
| ISSN: | 1438-0064 |
