DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Hypertree-Width and Related Hypergraph Invariants

Isolde Adler, Georg Gottlob, Martin Grohe


We study the notion of hypertree-width of hypergraphs. We prove that, up to a constant factor, hypertree-width is the same as a number of other hypergraph invariants that resemble graph invariants such as bramble-number, branch-width, linkedness, and the minimum number of cops required to win Seymour and Thomas's robber and cops game.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional