The complexity of computing minimal unidirectional covering sets (Q372959): Difference between revisions

Revision as of 22:53, 6 July 2024

scientific article; zbMATH DE number 5713750

The Complexity of Computing Minimal Unidirectional Covering Sets

Language	Label	Description	Also known as
English	The complexity of computing minimal unidirectional covering sets	scientific article; zbMATH DE number 5713750	The Complexity of Computing Minimal Unidirectional Covering Sets

Statements

instance of

scholarly article

0 references

title

The complexity of computing minimal unidirectional covering sets (English)

0 references

The Complexity of Computing Minimal Unidirectional Covering Sets (English)

0 references

0 references

0 references

0 references

0 references

0 references

Theory of Computing Systems

0 references

Lecture Notes in Computer Science

0 references

publication date

21 October 2013

0 references

28 May 2010

0 references

full work available at URL

https://arxiv.org/abs/0901.3692

0 references

zbMATH Keywords

computational social choice

0 references

computational complexity

0 references

minimal upward covering sets

0 references

minimal downward covering sets

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Ranking Tournaments

0 references

The complexity of computing minimal unidirectional covering sets

0 references

Q3266133

0 references

On the possibility of reasonable consistent majoritarian choice: Some positive results

0 references

Q3624140

0 references

Computing the minimal covering set

0 references

The Computational Complexity of Choice Sets

0 references

A computational analysis of the tournament equilibrium set

0 references

The Boolean Hierarchy I: Structural Properties

0 references

The Boolean Hierarchy II: Applications

0 references

Computational Aspects of Cooperative Game Theory

0 references

Exact analysis of Dodgson elections

0 references

Covering sets and a new Condorcet choice correspondence

0 references

Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete

0 references

On the computational cost of disjunctive logic programming: Propositional case

0 references

The complexity class θp2: Recent results and applications in AI and modal logic

0 references

Condorcet Social Choice Functions

0 references

Q4198056

0 references

Hybrid Elections Broaden Complexity-Theoretic Resistance to Control

0 references

Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP

0 references

Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

0 references

The complexity of Kemeny elections

0 references

The Minimization Problem for Boolean Formulas

0 references

The difference and truth-table hierarchies for NP

0 references

A comparison of polynomial time reducibilities

0 references

Tournament solutions and majority voting

0 references

The Proof That a Game May Not Have a Solution

0 references

Q4369423

0 references

Q5844986

0 references

Q4298260

0 references

The complexity of facets (and some facets of complexity)

0 references

Q4743737

0 references

Complexity theory and cryptology. An introduction to cryptocomplexity.

0 references

Exact complexity of the winner problem for Young elections

0 references

The polynomial-time hierarchy

0 references

The minimum equivalent DNF problem and shortest implicants

0 references

Relative complexity of checking and evaluating

0 references

More complicated questions about maxima and minima, and some closures of NP

0 references

Bounded Query Classes

0 references

Banks winners in tournaments are difficult to recognize

0 references

Extending Condorcet's rule

0 references

Identifiers

zbMATH Open document ID

1286.68179

0 references

1284.68288

0 references

DOI

10.1007/s00224-012-9437-9

0 references

10.1007/978-3-642-13073-1_27

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:372959

@@ Property / cites work @@
+Ranking Tournaments
@@ Property / cites work: Ranking Tournaments / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of computing minimal unidirectional covering sets
+Normal rank
@@ Property / cites work @@
+Q3266133
@@ Property / cites work: Q3266133 / rank @@
+Normal rank
@@ Property / cites work @@
+On the possibility of reasonable consistent majoritarian choice: Some positive results
+Normal rank
@@ Property / cites work @@
+Q3624140
@@ Property / cites work: Q3624140 / rank @@
+Normal rank
@@ Property / cites work @@
+Computing the minimal covering set
@@ Property / cites work: Computing the minimal covering set / rank @@
+Normal rank
@@ Property / cites work @@
+The Computational Complexity of Choice Sets
@@ Property / cites work: The Computational Complexity of Choice Sets / rank @@
+Normal rank
@@ Property / cites work @@
+A computational analysis of the tournament equilibrium set
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy I: Structural Properties
@@ Property / cites work: The Boolean Hierarchy I: Structural Properties / rank @@
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy II: Applications
@@ Property / cites work: The Boolean Hierarchy II: Applications / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Aspects of Cooperative Game Theory
@@ Property / cites work: Computational Aspects of Cooperative Game Theory / rank @@
+Normal rank
@@ Property / cites work @@
+Exact analysis of Dodgson elections
@@ Property / cites work: Exact analysis of Dodgson elections / rank @@
+Normal rank
@@ Property / cites work @@
+Covering sets and a new Condorcet choice correspondence
+Normal rank
@@ Property / cites work @@
+Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
+Normal rank
@@ Property / cites work @@
+On the computational cost of disjunctive logic programming: Propositional case
+Normal rank
@@ Property / cites work @@
+The complexity class θp2: Recent results and applications in AI and modal logic
+Normal rank
@@ Property / cites work @@
+Condorcet Social Choice Functions
@@ Property / cites work: Condorcet Social Choice Functions / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
+Normal rank
@@ Property / cites work @@
+Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
+Normal rank
@@ Property / cites work @@
+Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
+Normal rank
@@ Property / cites work @@
+The complexity of Kemeny elections
@@ Property / cites work: The complexity of Kemeny elections / rank @@
+Normal rank
@@ Property / cites work @@
+The Minimization Problem for Boolean Formulas
@@ Property / cites work: The Minimization Problem for Boolean Formulas / rank @@
+Normal rank
@@ Property / cites work @@
+The difference and truth-table hierarchies for NP
@@ Property / cites work: The difference and truth-table hierarchies for NP / rank @@
+Normal rank
@@ Property / cites work @@
+A comparison of polynomial time reducibilities
@@ Property / cites work: A comparison of polynomial time reducibilities / rank @@
+Normal rank
@@ Property / cites work @@
+Tournament solutions and majority voting
@@ Property / cites work: Tournament solutions and majority voting / rank @@
+Normal rank
@@ Property / cites work @@
+The Proof That a Game May Not Have a Solution
@@ Property / cites work: The Proof That a Game May Not Have a Solution / rank @@
+Normal rank
@@ Property / cites work @@
+Q4369423
@@ Property / cites work: Q4369423 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5844986
@@ Property / cites work: Q5844986 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of facets (and some facets of complexity)
+Normal rank
@@ Property / cites work @@
+Q4743737
@@ Property / cites work: Q4743737 / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity theory and cryptology. An introduction to cryptocomplexity.
+Normal rank
@@ Property / cites work @@
+Exact complexity of the winner problem for Young elections
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+The minimum equivalent DNF problem and shortest implicants
+Normal rank
@@ Property / cites work @@
+Relative complexity of checking and evaluating
@@ Property / cites work: Relative complexity of checking and evaluating / rank @@
+Normal rank
@@ Property / cites work @@
+More complicated questions about maxima and minima, and some closures of NP
+Normal rank
@@ Property / cites work @@
+Bounded Query Classes
@@ Property / cites work: Bounded Query Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Banks winners in tournaments are difficult to recognize
+Normal rank
@@ Property / cites work @@
+Extending Condorcet's rule
@@ Property / cites work: Extending Condorcet's rule / rank @@
+Normal rank