On the complexity of kings
From MaRDI portal
Publication:846367
DOI10.1016/j.tcs.2009.10.015zbMath1231.05112MaRDI QIDQ846367
Hemaspaandra, Lane A., Edith Hemaspaandra, Osamu Watanabe, Till Tantau
Publication date: 9 February 2010
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.10.015
05C12: Distance in graphs
05C20: Directed graphs (digraphs), tournaments
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The radii of n-partite tournaments
- Some observations on NP real numbers and P-selective sets
- Reductions on NP and p-selective sets
- Kings in \(k\)-partite tournaments
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- The complexity of finding top-Toda-equivalence-class members
- Succinct representations of graphs
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- The Complexity of Finding Paths in Graphs with Bounded Independence Number
- On the Complexity of Kings
- SOFSEM 2006: Theory and Practice of Computer Science