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 InvariantsConference paper

Authors: Isolde Adler 1; Georg Gottlob ORCID2; Martin Grohe ORCID3

  • 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.

https://doi.org/10.46298/dmtcs.3424
Source: HAL:hal-01184381v1
Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] hypergraphs, tree decompositions, hypertree width
Funding:
    Source : OpenAIRE Graph
  • Complementary Approaches to Constraint Satisfaction; Code: P 17222

7 Documents citing this article

Share and export

Consultation statistics

This page has been seen 597 times.
This article's PDF has been downloaded 994 times.