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 hierarchytournamentssuccinct representations

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Distance in graphs (05C12) 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

• 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?)
• Complete sets and the polynomial-time hierarchy
• Generalizations of tournaments: A survey
• 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

(5)

• On the Complexity of Kings
• Finding kings in tournaments
• The problem of kings
• The complexity of finding (approximate sized) distance-\(d\) dominating set in tournaments
• The problem of the kings

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)