On Minimal Constraint Networks

On Minimal Constraint Networks

Показать другие версии (1)

In a minimal binary constraint network, every tuple of a constraint relation can be extended to a solution. The tractability or intractability of computing a solution to such a minimal network was a long standing open question. Dechter conjectured this computation problem to be NP-hard. We prove thi...

Полное описание

Библиографические подробности
Главный автор:	Gottlob, G
Формат:	Journal article
Язык:	English
Опубликовано:	2011

Схожие документы

On Minimal Constraint Networks
по: Gottlob, G
Опубликовано: (2011)

On Tractable Queries and Constraints
по: Gottlob, G, и др.
Опубликовано: (1999)

Semantic acyclicity under constraints
по: Gottlob, G, и др.
Опубликовано: (2016)

Semantic acyclicity under constraints
по: Barceló, P, и др.
Опубликовано: (2016)

Conditional Constraint Satisfaction: Logical Foundations and Complexity
по: Gottlob, G, и др.
Опубликовано: (2007)

HyperConsistency Width For Constraint Satisfaction
по: Marnette, B, и др.
Опубликовано: (2009)

Reasoning under minimal upper bounds in propositional logic
по: Eiter, T, и др.
Опубликовано: (2006)

Reasoning under minimal upper bounds in propositional logic
по: Eiter, T, и др.
Опубликовано: (2006)

Identifying the Minimal Transversals of a Hypergraph and Related Problems
по: Eiter, T, и др.
Опубликовано: (1995)

Energy Consumption Minimization with SNR Constraint for Wireless Powered Communication Networks
по: Kuei-Ping Shih, и др.
Опубликовано: (2024-08-01)

Datalog±: a unified approach to ontologies and integrity constraints.
по: Calì, A, и др.
Опубликовано: (2009)

Datalog±: A Unified Approach to Ontologies and Integrity Constraints
по: Calì, A, и др.
Опубликовано: (2009)

Fast and parallel decomposition of constraint satisfaction problems
по: Gottlob, G, и др.
Опубликовано: (2020)

Fast and parallel decomposition of constraint satisfaction problems
по: Gottlob, G, и др.
Опубликовано: (2022)

Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics.
по: Abramsky, S, и др.
Опубликовано: (2013)

Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics
по: Abramsky, S, и др.
Опубликовано: (2013)

The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions
по: Gottlob, G, и др.
Опубликовано: (2005)

On the Interaction of Existential Rules and Equality Constraints in Ontology Querying
по: Calì, A, и др.
Опубликовано: (2012)

Iterative Schemes for Convex Minimization Problems with Constraints
по: Lu-Chuan Ceng, и др.
Опубликовано: (2014-01-01)

Methods for Minimizing the Savage Function with Various Constraints
по: Anatol Godonoaga, и др.
Опубликовано: (2024-03-01)

Minimal constraints in the parity formulation of optimization problems
по: Martin Lanthaler, и др.
Опубликовано: (2021-01-01)

Cost-minimizing team hires with participation constraint.
по: Heli Sun, и др.
Опубликовано: (2018-01-01)

Tree projections and constraint optimization problems: Fixed-parameter tractability and parallel algorithms
по: Gottlob, G, и др.
Опубликовано: (2017)

Age of Synchronization Minimization Algorithms in Wireless Networks with Random Updates under Throughput Constraints
по: Yuqiao He, и др.
Опубликовано: (2023-09-01)

Semantic width and the fixed-parameter tractability of constraint satisfaction problems
по: Chen, H, и др.
Опубликовано: (2020)

Current LHC constraints on minimal universal extra dimensions
по: Nicolas Deutschmann, и др.
Опубликовано: (2017-08-01)

Makespan-Minimizing Heterogeneous Task Allocation under Temporal Constraints
по: Byeong-Min Jeong, и др.
Опубликовано: (2023-12-01)

IAE Minimization in Sliding Mode Control With Input and Velocity Constraints
по: Mateusz Pietrala, и др.
Опубликовано: (2022-01-01)

Minimizing the Duration of Repetitive Construction Processes with Work Continuity Constraints
по: Piotr Jaśkowski, и др.
Опубликовано: (2019-03-01)

What ξ? Cosmological constraints on the non-minimal coupling constant
по: Orest Hrycyna
Опубликовано: (2017-05-01)

FUMILI-based minimization with constraints using method of elimination of differentials
по: Kurbatov Vladimir, и др.
Опубликовано: (2019-01-01)

A strict inequality for the minimization of the Willmore functional under isoperimetric constraint
по: Mondino, A, и др.
Опубликовано: (2021)

Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints
по: Bruno Prata, и др.
Опубликовано: (2022-12-01)

Convex separable minimization problems with a linear constraint and bounded variables
по: Stefan M. Stefanov
Опубликовано: (2005-01-01)

Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity Constraints
по: Yasuaki Kobayashi, и др.
Опубликовано: (2025-02-01)

Delay Minimization in RIS-Assisted URLLC Systems under Reliability Constraints
по: Xiaoyang Song, и др.
Опубликовано: (2023-05-01)

Farmer’s opinion to minimize the constraints in scientific dairy farming practices of Nalanda
по: SANJEEV KUMAR, и др.
Опубликовано: (2016-08-01)

Algorithms for Symmetric Submodular Function Minimization under Hereditary Constraints and Generalizations
по: Goemans, Michel X., и др.
Опубликовано: (2013)

Comparison of appointment scheduling perspectives between cost minimization and service level constraint
по: Wong, Kai Qin
Опубликовано: (2021)

Existence and limit behavior of constraint minimizers for elliptic equations with two nonlocal terms
по: Xincai Zhu, и др.
Опубликовано: (2024-08-01)