Some Tractable Win-Lose Games
From MaRDI portal
Publication:3010417
DOI10.1007/978-3-642-20877-5_36zbMath1332.91011arXiv1010.5951MaRDI QIDQ3010417
Nagarajan Krishnamurthy, Samir Datta
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)
Related Items
Cites Work
- Unnamed Item
- 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
- Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
- 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