Constraint solving via fractional edge covers

DOI10.1145/1109557.1109590zbMath1192.68642arXiv1711.04506OpenAlexW2952861917MaRDI QIDQ3581534

Publication date: 16 August 2010

Published in: ACM Transactions on Algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphs constraint satisfaction hypertree width fractional edge covers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (48)

Structural tractability of counting of solutions to conjunctive queries ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Structural decompositions for problems with global constraints ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Constraint satisfaction with bounded treewidth revisited ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Answering conjunctive queries with inequalities ⋮ Regularizing conjunctive features for classification ⋮ Covers of Query Results ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ Algorithms for Propositional Model Counting ⋮ HyperBench ⋮ Fractional covers of hypergraphs with bounded multi-intersection ⋮ Computing optimal hypertree decompositions with SAT ⋮ Computing partial hypergraphs of bounded width ⋮ Linear Programs with Conjunctive Database Queries ⋮ Computing a partition function of a generalized pattern-based energy over a semiring ⋮ Computing hypergraph width measures exactly ⋮ Dynamic Management of Heuristics for Solving Structured CSPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Constraint satisfaction with succinctly specified relations ⋮ An annotated bibliography on guaranteed graph searching ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Fractional Edge Cover Number of Model RB ⋮ Hypertree width and related hypergraph invariants ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ Tractable structures for constraint satisfaction with truth tables ⋮ On the power of structural decompositions of graph-based representations of constraint problems ⋮ Algorithms for propositional model counting ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems ⋮ Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value ⋮ Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints ⋮ Tree-Width for First Order Formulae ⋮ Evaluating Datalog via tree automata and cycluits ⋮ Tree Projections: Game Characterization and Computational Aspects ⋮ A more general theory of static approximations for conjunctive queries ⋮ Fast and parallel decomposition of constraint satisfaction problems ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Unnamed Item ⋮ Structural tractability of enumerating CSP solutions ⋮ Constructing NP-intermediate problems by blowing holes with parameters of various properties ⋮ Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT ⋮ ON THE EDGE COVER POLYNOMIAL OF CERTAIN GRAPHS

This page was built for publication: Constraint solving via fractional edge covers