The complexity of selecting maximal solutions

DOI10.1006/inco.1995.1087zbMath0834.68045OpenAlexW2026565317MaRDI QIDQ1893737

Seinosuke Toda, Zhi-Zhong Chen

Publication date: 2 August 1995

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/83421

zbMATH Keywords

combinatorial optimization problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Related Items (16)

Complexity results for some eigenvector problems ⋮ Witnesses for Answer Sets of Logic Programs ⋮ Counting minimal unsatisfiable subsets ⋮ The operators min and max on the polynomial hierarchy ⋮ Generating all maximal models of a Boolean expression ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ Finding similar/diverse solutions in answer set programming ⋮ Minimal sets on propositional formulae. Problems and reductions ⋮ Tractability of explaining classifier decisions ⋮ Detecting and repairing anomalous evolutions in noisy environments. Logic programming formalization and complexity results ⋮ The Complexity Landscape of Outcome Determination in Judgment Aggregation ⋮ Trichotomies in the complexity of minimal inference ⋮ Determining inference semantics for disjunctive logic programs ⋮ Semantical and computational aspects of Horn approximations ⋮ Complexity and expressive power of deterministic semantics for DATALOG\(^ \neg\). ⋮ On the query complexity of selecting minimal sets for monotone predicates

This page was built for publication: The complexity of selecting maximal solutions