Some Tractable Win-Lose Games
From MaRDI portal
Publication:3010417
DOI10.1007/978-3-642-20877-5_36zbMath1332.91011arXiv1010.5951MaRDI QIDQ3010417
Samir Datta, Nagarajan Krishnamurthy
Publication date: 1 July 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1010.5951
68Q25: Analysis of algorithms and problem complexity
91A10: Noncooperative games
91A43: Games involving graphs
05C85: Graph algorithms (graph-theoretic aspects)
05C57: Games on graphs (graph-theoretic aspects)
Cites Work
- An approach to the subgraph homeomorphism problem
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- On the complexity of the parity argument and other inefficient proofs of existence
- Non-cooperative games
- Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
- Settling the complexity of computing two-player Nash equilibria
- Dividing a Graph into Triconnected Components
- The Complexity of Computing a Nash Equilibrium
- A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
- Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
- Unnamed Item
- Unnamed Item