We introduce hyper-D-width and hyper-T-width as the first stable (see Definition 3) measures of connectivity for hypergraphs. After studying some of their properties and, in particular, proposing an algorithm for computing nearly optimal hyper-T-decomposition when hyper-T-width is constant, we introduce some applications of hyper-D-width and hyper-T-width in solving hard problems such as minimum vertex cover, minimum dominating set, and multicut.
展开▼
