{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T01:08:02Z","timestamp":1725757682601},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319038971"},{"type":"electronic","value":"9783319038988"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03898-8_29","type":"book-chapter","created":{"date-parts":[[2013,11,19]],"date-time":"2013-11-19T02:57:26Z","timestamp":1384829846000},"page":"348-360","source":"Crossref","is-referenced-by-count":1,"title":["Treewidth and Pure Nash Equilibria"],"prefix":"10.1007","author":[{"given":"Antonis","family":"Thomas","sequence":"first","affiliation":[]},{"given":"Jan","family":"van Leeuwen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"29_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0004-3702(00)00075-8","volume":"125","author":"A. Becker","year":"2001","unstructured":"Becker, A., Geiger, D.: A sufficiently fast algorithm for finding close to optimal clique trees. Artif. Intell.\u00a0125(1-2), 3\u201317 (2001)","journal-title":"Artif. Intell."},{"issue":"6","key":"29_CR2","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"26","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput\u00a026(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput"},{"issue":"3","key":"29_CR3","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J.\u00a051(3), 255\u2013269 (2008)","journal-title":"Comput. J."},{"issue":"8","key":"29_CR4","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. and Syst. Sciences\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. and Syst. Sciences"},{"key":"29_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1007\/978-3-642-04128-0_57","volume-title":"Algorithms - ESA 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 635\u2013646. Springer, Heidelberg (2009)"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. J. ACM\u00a056(3) (2009)","DOI":"10.1145\/1516512.1516516"},{"key":"29_CR7","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Computing pure Nash equilibria in graphical games via markov random fields. In: Feigenbaum, J., et al. (eds.) ACM Conference on Electronic Commerce, pp. 91\u201399 (2006)","DOI":"10.1145\/1134707.1134718"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Schoenebeck, G., Valiant, G., Valiant, P.: On the complexity of Nash equilibria of action-graph games. In: ACM-SIAM SODA, pp. 710\u2013719 (2009)","DOI":"10.1137\/1.9781611973068.78"},{"issue":"1","key":"29_CR9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput.\u00a039(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"key":"29_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, NY (1999)"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Drucker, A.: New limits to classical and quantum instance compression. In: FOCS 2012, pp. 609\u2013618 (2012)","DOI":"10.1109\/FOCS.2012.71"},{"issue":"1","key":"29_CR12","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci.\u00a0410(1), 53\u201361 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR13","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1613\/jair.1683","volume":"24","author":"G. Gottlob","year":"2005","unstructured":"Gottlob, G., Greco, G., Scarcello, F.: Pure Nash equilibria: hard and easy games. J. Artif. Intell. Res.\u00a024, 357\u2013406 (2005)","journal-title":"J. Artif. Intell. Res."},{"key":"29_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11604686_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"G. Gottlob","year":"2005","unstructured":"Gottlob, G., Grohe, M., Musliu, N., Samer, M., Scarcello, F.: Hypertree decompositions: structure, algorithms, and applications. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 1\u201315. Springer, Heidelberg (2005)"},{"issue":"38-40","key":"29_CR15","doi-asserted-by":"publisher","first-page":"3901","DOI":"10.1016\/j.tcs.2009.05.030","volume":"410","author":"G. Greco","year":"2009","unstructured":"Greco, G., Scarcello, F.: On the complexity of constrained Nash equilibria in graphical games. Theor. Comput. Sci.\u00a0410(38-40), 3901\u20133924 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR16","unstructured":"Jiang, A.X., Leyton-Brown, K.: Computing pure Nash equilibria in symmetric action graph games. In: Cohn, A. (ed.) AAAI 2007, vol.\u00a01, pp. 79\u201385. AAAI Press (2007)"},{"key":"29_CR17","unstructured":"Jiang, A.X., Safari, M.A.: Pure Nash equilibria: complete characterization of hard and easy graphical games. In: van der Hoek, W., et al. (eds.) AAMAS 2010, pp. 199\u2013206 (2010)"},{"issue":"1","key":"29_CR18","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.geb.2010.10.012","volume":"71","author":"A.X. Jiang","year":"2011","unstructured":"Jiang, A.X., Leyton-Brown, K., Bhat, N.A.R.: Action-graph games. Games and Economic Behavior\u00a071(1), 141\u2013173 (2011)","journal-title":"Games and Economic Behavior"},{"key":"29_CR19","unstructured":"Kearns, M.J., Littman, M.L., Singh, S.P.: Graphical models for game theory. In: Breeses, J.S., Koller, D. (eds.) UAI 2001, pp. 253\u2013260. Morgan Kaufmann (2001)"},{"issue":"1","key":"29_CR20","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D. Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory of Computing\u00a06(1), 85\u2013112 (2010)","journal-title":"Theory of Computing"},{"key":"29_CR21","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Univ. Press, NY (2006)"},{"key":"29_CR22","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"30","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors II: Algorithmic aspects of tree-width. J. Algorithms\u00a030, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"29_CR23","unstructured":"Thomas, A.: Games on Graphs - The Complexity of Pure Nash Equilibria, Technical Report UU-CS-2011-024, Dept. of Information and Computing Sciences, Utrecht University (2011)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03898-8_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T06:55:22Z","timestamp":1558680922000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03898-8_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319038971","9783319038988"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03898-8_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}