On the complexity of kings

DOI10.1016/J.TCS.2009.10.015MaRDI QIDQ846367zbMATH OpenOpenAlexFDO

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

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

diameterkingspolynomial hierarchysuccinct representationstournaments

Mathematics Subject Classification ID

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

Recommendations

• On the Complexity of Kings
• Finding kings in tournaments
• Kings in strong tournaments.
• Kings in quasi-transitive digraphs
• Kings in semicomplete multipartite digraphs

Cites work

• Complete sets and the polynomial-time hierarchy
• Generalizations of tournaments: A survey
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1543295 (Why is no real title available?)
• Kings in \(k\)-partite tournaments
• Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
• On the Complexity of Kings
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Reductions on NP and p-selective sets
• SOFSEM 2006: Theory and Practice of Computer Science
• Some observations on NP real numbers and P-selective sets
• Succinct representations of graphs
• The Complexity of Finding Paths in Graphs with Bounded Independence Number
• The complexity of finding top-Toda-equivalence-class members
• The polynomial-time hierarchy
• The radii of n-partite tournaments

Cited in

(8)

• The problem of the kings
• The problem of kings
• Finding kings in tournaments
• The complexity of finding (approximate sized) distance-d dominating set in tournaments
• On the Complexity of Kings
• AI Planning Languages Semantics
• Verified SAT-Based AI Planning
• Upper Bounding Diameters of State Spaces of Factored Transition Systems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q846367)