HyperBench

DOI10.1145/3440015zbMath1499.68269arXiv2009.01769OpenAlexW3178614413WikidataQ114071207 ScholiaQ114071207MaRDI QIDQ5102056

Georg Gottlob, Wolfgang Fischl, Davide Mario Longo, Reinhard Pichler

Publication date: 6 September 2022

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2009.01769

zbMATH Keywords

constraint satisfactionquery answeringhypergraph decomposition methods

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items

Fractional covers of hypergraphs with bounded multi-intersection ⋮ Computing optimal hypertree decompositions with SAT ⋮ Computing partial hypergraphs of bounded width ⋮ Fast and parallel decomposition of constraint satisfaction problems

Uses Software

• MiniCon
• JGraphT
• LUBM
• Hypergraph Library
• LogicBlox
• EmptyHeaded
• iBench
• HyperBench

Cites Work

• Computing hypergraph width measures exactly
• Hypertree decompositions and tractable queries
• Weighted hypertree decompositions and optimal query plans
• MiniCon: a scalable algorithm for answering queries using views
• Hypertree width and related hypergraph invariants
• Approximating fractional hypertree width
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Constraint solving via fractional edge covers
• A compressed Generalized Hypertree Decomposition-based solving technique for non-binary Constraint Satisfaction Problems
• Size Bounds for Factorised Representations of Query Results
• Joins via Geometric Resolutions
• JGraphT—A Java Library for Graph Data Structures and Algorithms
• Computing Optimal Hypertree Decompositions
• A backtracking-based algorithm for hypertree decomposition
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities