4 citations · 13 across the 12 of their papers we have counts for
Showing 2010Show all
2 papers · 1 filter
cs.GT2010
Some Tractable Win-Lose Games
Samir Datta, Nagarajan Krishnamurthy
Determining a Nash equilibrium in a -player non-zero sum game is known to be PPAD-hard (Chen and Deng (2006), Chen, Deng and Teng (2009)). The problem, even when restricted to w…
cs.CC2010
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs
Samir Datta, Raghav Kulkarni, Raghunath Tewari +1
We investigate the space complexity of certain perfect matching problems over bipartite graphs embedded on surfaces of constant genus (orientable or non-orientable). We show that t…