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

Boolean formulasBoolean isomorphismcomputational complexitygame isomorphismgraph isomorphismsuccinct representations

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Analysis of algorithms and problem complexity (68Q25) 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

(11)

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

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)