Tractable Optimization Problems through Hypergraph-Based Structural Restrictions

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

Mathematics Subject Classification ID

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