On the complexity of kings

DOI10.1016/j.tcs.2009.10.015zbMath1231.05112OpenAlexW3005353630MaRDI QIDQ846367

Till Tantau, Osamu Watanabe, Edith Hemaspaandra, Hemaspaandra, Lane A.

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

zbMATH Keywords

diametertournamentspolynomial hierarchykingssuccinct representations

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• 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
• Generalizations of tournaments: A survey
• The Complexity of Finding Paths in Graphs with Bounded Independence Number
• On the Complexity of Kings
• SOFSEM 2006: Theory and Practice of Computer Science

This page was built for publication: On the complexity of kings