Isolde Adler ; Georg Gottlob ; Martin Grohe
-
Hypertree-Width and Related Hypergraph Invariants
dmtcs:3424 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
-
https://doi.org/10.46298/dmtcs.3424
Hypertree-Width and Related Hypergraph Invariants
Authors: Isolde Adler 1; Georg Gottlob 2; Martin Grohe 3
NULL##NULL##NULL
Isolde Adler;Georg Gottlob;Martin Grohe
1 Mathematisches Institut, Abteilung für Mathematische Logik
2 Institut für Informationssysteme [Wien]
3 Institut fur Informatik
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.