On the complexity of kings

DOI10.1016/J.TCS.2009.10.015zbMATH Open1231.05112OpenAlexW3005353630MaRDI QIDQ846367FDOQ846367

Till Tantau, Osamu Watanabe, Edith Hemaspaandra, 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

Recommendations

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

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)

Cites Work

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

Cited In (2)

• The problem of kings
• 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)