Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Hypertree-Width and ...
Conference paper

Hypertree-Width and Related Hypergraph Invariants

Isolde Adler (1), Georg Gottlob ORCID (2), Martin Grohe ORCID (3)
(1) Mathematisches Institut, Abteilung für Mathematische Logik
(2) Institut für Informationssysteme [Wien]
(3) Institut fur Informatik
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3424
License
https://about.hal.science/hal-authorisation-v1
P 17222
Indicators
1097
Views
5540
Downloads

Hypertree-Width and Related Hypergraph Invariants

Isolde Adler (1), Georg Gottlob ORCID (2), Martin Grohe ORCID (3)
(1) Mathematisches Institut, Abteilung für Mathematische Logik
(2) Institut für Informationssysteme [Wien]
(3) Institut fur Informatik
Abstract
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • hypergraphs
  • tree decompositions
  • hypertree width
Cited by

Source: OpenCitations

  • Uniform Constraint Satisfaction Problems and Database Theory

    Lecture notes in computer science

    Authors : Francesco Scarcello ORCID, Georg Gottlob ORCID, Gianluigi Greco ORCID

    Journal reference : Volume , 2008, pp. 156-195

    DOI : 10.1007/978-3-540-92800-3_7
  • Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints

    French digital mathematics library (Numdam)

    Authors : Zineb Habbas ORCID, Kamal Amroun ORCID, Daniel Singer ORCID

    Journal reference : Volume 50, 2015, pp. 241-267

    DOI : 10.1051/ro/2015017
  • A compressed Generalized Hypertree Decomposition-based solving technique for non-binary Constraint Satisfaction Problems

    AI Communications

    Authors : Kamal Amroun ORCID, Zineb Habbas ORCID, Wassila Aggoune-Mtalaa ORCID

    Journal reference : Volume 29, 2016, pp. 371-392

    DOI : 10.3233/aic-150694
  • The Structure of Tractable Constraint Satisfaction Problems

    Lecture notes in computer science

    Authors : Martin Grohe ORCID

    Journal reference : Volume , 2006, pp. 58-72

    DOI : 10.1007/11821069_5
  • An annotated bibliography on guaranteed graph searching

    Theoretical Computer Science

    Authors : Fedor V. Fomin ORCID, Dimitrios M. Thilikos ORCID

    Journal reference : Volume 399, 2008, pp. 236-245

    DOI : 10.1016/j.tcs.2008.02.040
  • HSJ-Solver: a new method based on GHD for answering conjunctive queries and solving constraint satisfaction problems

    Applied Intelligence

    Authors : Zineb Younsi, Kamal Amroun ORCID, Farida Bouarab-Dahmani, Sofia Bennai

    Journal reference : Volume 53, 2022, pp. 17226-17239

    DOI : 10.1007/s10489-022-04361-y
  • HyperConsistency Width for Constraint Satisfaction: Algorithms and Complexity Results

    Lecture notes in computer science

    Authors : Georg Gottlob ORCID, Gianluigi Greco ORCID, Bruno Marnette

    Journal reference : Volume , 2009, pp. 87-99

    DOI : 10.1007/978-3-642-02029-2_9
Preview
Loading PDF preview...