On the Complexity of Game Isomorphism

DOI10.1007/978-3-540-74456-6_50MaRDI QIDQ3525601zbMATH OpenOpenAlexFDO

Authors Joaquim Gabarró, Alina García, Maria Serna

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74456-6_50

zbMATH Keywords

computational complexitygraph isomorphismBoolean formulasgame isomorphismsuccinct representationsBoolean isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Noncooperative games (91A10)

Recommendations

• The complexity of game isomorphism
• On the hardness of game equivalence under local isomorphism
• Weak isomorphism of extensive games.
• A note on isomorphism and strategic equivalence of cooperative games
• Equilibria problems on games: complexity versus succinctness

Cited in

(10)

• On the complexity of deciding bimatrix games similarity
• Some results of Maria Serna on strategic games: complexity of equilibria and models
• Games with uniqueness properties
• The complexity of game isomorphism
• Modeling and Isomorphisms of Positional Board Games
• Equilibria problems on games: complexity versus succinctness
• New Computational Paradigms
• On the hardness of game equivalence under local isomorphism
• Permissible four-strategy quantum extensions of classical games
• Weak isomorphism of extensive games.

This page was built for publication: On the Complexity of Game Isomorphism

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