The complexity of facets resolved
From MaRDI portal
Publication:1109565
DOI10.1016/0022-0000(88)90042-6zbMATH Open0655.68041DBLPjournals/jcss/PapadimitriouW88OpenAlexW2158505527WikidataQ59795818 ScholiaQ59795818MaRDI QIDQ1109565FDOQ1109565
Authors: Christos Papadimitriou, David Wolfe 
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6542
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Solution of a Large-Scale Traveling-Salesman Problem
- On certain polytopes associated with graphs
- On the symmetric travelling salesman problem II: Lifting theorems and facets
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The complexity of facets (and some facets of complexity)
- NP is as easy as detecting unique solutions
- On the unique satisfiability problem
- On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets
Cited In (61)
- Justifications for Description Logic Knowledge Bases Under the Fixed-Domain Semantics
- Super-reparametrizations of weighted CSPs: properties and optimization perspective
- Witnesses for Answer Sets of Logic Programs
- On the complexity of semantic self-minimization
- Finding optimal solutions with neighborly help
- Better approximations of non-Hamiltonian graphs
- An upper bound for the circuit complexity of existentially quantified Boolean formulas
- On the query complexity of selecting minimal sets for monotone predicates
- Computational approaches to finding and measuring inconsistency in arbitrary knowledge bases
- Towards a notion of unsatisfiable and unrealizable cores for LTL
- Homomorphisms of conjunctive normal forms.
- On the structure of some classes of minimal unsatisfiable formulas
- Removing redundancy from a clause
- The complexity of recognizing minimally tough graphs
- Using inconsistency measures for estimating reliability
- Selected topics on assignment problems
- Recognizing frozen variables in constraint satisfaction problems
- The complexity of variable minimal formulas
- Knapsack polytopes: a survey
- The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
- Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets
- A branch and bound algorithm for extracting smallest minimal unsatisfiable subformulas
- Finding read-once resolution refutations in systems of 2CNF clauses
- Complexity of stability
- Computing maximal autarkies with few and simple oracle queries
- Complexity Classifications for Logic-Based Argumentation
- A simplified way of proving trade-off results for resolution
- Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
- DP-Complete Problems Derived from Extremal NP-Complete Properties
- Accelerated deletion-based extraction of minimal unsatisfiable cores
- Density condensation of Boolean formulas
- On subclasses of minimal unsatisfiable formulas
- Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference.
- Two tractable subclasses of minimal unsatisfiable formulas
- A framework for handling logical inconsistencies in the fusion of Boolean knowledge bases
- Extension and equivalence problems for clause minimal formulae
- On the complexity of inconsistency measurement
- How Many Conflicts Does It Need to Be Unsatisfiable?
- An approach for extracting a small unsatisfiable core
- Redundancy in logic. I: CNF propositional formulae
- Using local search to find MSSes and MUSes
- On getting rid of the preprocessing minimization step in MUC-finding algorithms
- Finding Optimal Solutions With Neighborly Help.
- Understanding the complexity of axiom pinpointing in lightweight description logics
- On measuring inconsistency in definite and indefinite databases with denial constraints
- On the computational complexity of read once resolution decidability in 2CNF formulas
- Faster Extraction of High-Level Minimal Unsatisfiable Cores
- How to recycle your facets
- On the complexity of non-unique probe selection
- Computing smallest MUSes of quantified Boolean formulas
- Localising iceberg inconsistencies
- Computational complexity of quantified Boolean formulas with fixed maximal deficiency
- Dealing Automatically with Exceptions by Introducing Specificity in ASP
- Local-search extraction of mUSes
- Redundancy in logic. II: 2CNF and Horn propositional formulae
- Redundancy in logic. III: Non-monotonic reasoning
- On semidefinite least squares and minimal unsatisfiability
- Complexity of Stability.
- Strong inconsistency
- Semantic relevance
- Fixed-parameter tractability of satisfying beyond the number of variables
This page was built for publication: The complexity of facets resolved
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109565)
