The Parallel Complexity of Coloring Games

DOI10.1007/978-3-662-53354-3_3zbMath1403.91065OpenAlexW2513156480MaRDI QIDQ2819445

Guillaume Ducoffe

Publication date: 29 September 2016

Published in: Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53354-3_3

zbMATH Keywords

Nash equilibriumcomplexity of computinggraph gamesPTIME-hardness

Mathematics Subject Classification ID

Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Non-existence of stable social groups in information-driven networks, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, How long does it take for all users in a social network to choose their communities?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A theory of strict P-completeness
• Coalition formation games with separable preferences.
• NP-completeness in hedonic games
• Information-sharing in social networks
• Computing Stable Outcomes in Hedonic Games
• A Game Theoretic Approach for Efficient Graph Coloring
• Distributed Welfare Games
• Sharing the cost of multicast transmissions