Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
From MaRDI portal
Publication:3638082
DOI10.1007/978-3-642-02930-1_2zbMath1248.68246arXiv1209.3419OpenAlexW2155683758WikidataQ59259605 ScholiaQ59259605MaRDI QIDQ3638082
Georg Gottlob, Gianluigi Greco, Francesco Scarcello
Publication date: 14 July 2009
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1209.3419
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Structural decompositions for problems with global constraints ⋮ The Complexity of General-Valued CSPs ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. ⋮ Computing a partition function of a generalized pattern-based energy over a semiring ⋮ The Complexity of Valued CSPs ⋮ Coalition formation in social environments with logic-based agents1 ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
This page was built for publication: Tractable Optimization Problems through Hypergraph-Based Structural Restrictions