Computing partial hypergraphs of bounded width

DOI10.1016/J.DAM.2022.12.025MaRDI QIDQ2686128zbMATH OpenOpenAlexFDO

Authors Nabil Adrar, Philippe Jégou, Cyril Terrioux

Publication date 24 February 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2022.12.025

zbMATH Keywords

bounded treewidthpartial hypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Computing hypergraph width measures exactly
• Approximating fractional hypertree width
• Approximating fractional hypertree width
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries

Cites work

• A comparison of structural CSP decomposition methods
• Boolean-width of graphs
• Complexity of Finding Embeddings in a k-Tree
• Degrees of acyclicity for hypergraphs and relational database schemes
• Fundamentals of Computation Theory
• Graph minors. II. Algorithmic aspects of tree-width
• Handbook of constraint programming.
• scientific article; zbMATH DE number 3152801 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• Hybrid backtracking bounded by tree-decomposition of constraint networks
• HyperBench. A benchmark and tool for hypergraphs and empirical findings
• Incidence matrices and interval graphs
• Learning Markov networks: Maximum bounded tree-width graphs
• Maximum likelihood bounded tree-width Markov networks
• Maximum matching width: new characterizations and a fast algorithm for dominating set
• MiniCon: a scalable algorithm for answering queries using views
• Networks of constraints: Fundamental properties and applications to picture processing
• On rigid circuit graphs
• On the Desirability of Acyclic Database Schemes
• Parameterized Algorithms for Modular-Width
• Probabilistic graphical models.
• Properties and characterizations of k ‐trees
• Reasoning with probabilistic and deterministic graphical models. Exact algorithms
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Sparsity. Graphs, structures, and algorithms
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• The structure of graphs not admitting a fixed immersion

Cited in

(5)

• Decomposition of a hypergraph by partial-edge separators
• Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
• Computability of width of submodular partition functions
• Computing hypergraph width measures exactly
• The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications

Describes a project that uses

Uses Software

• HyperBench
• MiniCon

This page was built for publication: Computing partial hypergraphs of bounded width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2686128)