{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T09:25:36Z","timestamp":1770888336764,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2015,6,2]],"date-time":"2015-06-02T00:00:00Z","timestamp":1433203200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s10472-015-9461-y","type":"journal-article","created":{"date-parts":[[2015,6,1]],"date-time":"2015-06-01T05:47:26Z","timestamp":1433137646000},"page":"317-333","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games"],"prefix":"10.1007","volume":"77","author":[{"given":"Anja","family":"Rey","sequence":"first","affiliation":[]},{"given":"J\u00f6rg","family":"Rothe","sequence":"additional","affiliation":[]},{"given":"Hilmar","family":"Schadrack","sequence":"additional","affiliation":[]},{"given":"Lena","family":"Schend","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,2]]},"reference":[{"key":"9461_CR1","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1016\/j.artint.2012.09.006","volume":"195","author":"H Aziz","year":"2013","unstructured":"Aziz, H., Brandt, F., Seedig, H.: Computing desirable partitions in additively separable hedonic games. Artif. Intell. 195, 316\u2013334 (2013)","journal-title":"Artif. Intell."},{"issue":"3","key":"9461_CR2","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/s00224-012-9437-9","volume":"53","author":"D Baumeister","year":"2013","unstructured":"Baumeister, D., Brandt, F., Fischer, F., Hoffmann, J., Rothe, J.: The complexity of computing minimal unidirectional covering sets. Theory of Computing Systems 53(3), 467\u2013502 (2013)","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"9461_CR3","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/0304-3975(91)90160-4","volume":"84","author":"R Beigel","year":"1991","unstructured":"Beigel, R.: Bounded queries to SAT and the boolean hierarchy. Theor. Comput. Sci. 84(2), 199\u2013223 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"9461_CR4","doi-asserted-by":"crossref","unstructured":"Beigel, R., Hemachandra, L., Wechsung, G.: On the power of probabilistic polynomial time: P NP [ log ] \u2286 PP $\\mathrm {P^{NP[log]}}\\subseteq PP$ . In: Proceedings of the 4th Structure in Complexity Theory Conference, pp 225\u2013227. IEEE Computer Society Press, June (1989)","DOI":"10.1109\/SCT.1989.41828"},{"key":"9461_CR5","doi-asserted-by":"publisher","unstructured":"Brams, S., Fishburn, P. In: Arrow, K., Sen, A., Suzumura, K. (eds.) : Handbook of Social Choice and Welfare, volume 1, pages 173\u2013236. North-Holland (2002)","DOI":"10.1016\/S1574-0110(02)80008-X"},{"key":"9461_CR6","unstructured":"Brandt, F., Conitzer, V., Endriss, U. Computational social choice. In: Wei\u00df, G. (ed.) : Multiagent Systems, pp 213\u2013283. MIT Press, second edition (2013)"},{"issue":"6","key":"9461_CR7","doi-asserted-by":"publisher","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J Cai","year":"1988","unstructured":"Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The boolean hierarchy I: Structural properties. SIAM J. Comput. 17(6), 1232\u20131252 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9461_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J Cai","year":"1989","unstructured":"Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The boolean hierarchy II: Applications. SIAM J. Comput. 18(1), 95\u2013111 (1989)","journal-title":"SIAM J. Comput."},{"key":"9461_CR9","doi-asserted-by":"crossref","unstructured":"Chalkiadakis, G., Elkind, E., Wooldridge, M.: Computational Aspects of Cooperative Game Theory. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool Publishers (2011)","DOI":"10.2200\/S00355ED1V01Y201107AIM016"},{"issue":"3","key":"9461_CR10","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF01303054","volume":"28","author":"R Chang","year":"1995","unstructured":"Chang, R., Kadin, J.: On computing boolean connectives of characteristic functions. Mathematical Systems Theory 28(3), 173\u2013198 (1995)","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"9461_CR11","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s00355-006-0104-4","volume":"26","author":"D Dimitrov","year":"2006","unstructured":"Dimitrov, D., Borm, P., Hendrickx, R., Sung, S.: Simple priorities and core stability in hedonic games. Soc. Choice Welf. 26(2), 421\u2013433 (2006)","journal-title":"Soc. Choice Welf."},{"key":"9461_CR12","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H, Freeman and Company (1979)"},{"issue":"3","key":"9461_CR13","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L Hemachandra","year":"1989","unstructured":"Hemachandra, L.: The strong exponential hierarchy collapses. J. Comput. Syst. Sci. 39(3), 299\u2013322 (1989)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9461_CR14","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/S0020-0190(97)00219-6","volume":"65","author":"E Hemaspaandra","year":"1998","unstructured":"Hemaspaandra, E., Rothe, J.: Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP. Inf. Process. Lett. 65(3), 151\u2013156 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"9461_CR15","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1145\/268999.269002","volume":"44","author":"E Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Exact analysis of Dodgson elections: Lewis Carroll\u2019s 1876 voting system is complete for parallel access to NP. J. ACM 44(6), 806\u2013825 (1997a)","journal-title":"J. ACM"},{"issue":"2","key":"9461_CR16","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/261342.261344","volume":"28","author":"E Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Raising NP lower bounds to parallel NP lower bounds. SIGACT News 28(2), 2\u201313 (1997b)","journal-title":"SIGACT News"},{"issue":"3","key":"9461_CR17","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.tcs.2005.08.031","volume":"349","author":"E Hemaspaandra","year":"2005","unstructured":"Hemaspaandra, E., Spakowski, H., Vogel, J.: The complexity of Kemeny elections. Theor. Comput. Sci. 349(3), 382\u2013391 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9461_CR18","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1051\/ita:2005041","volume":"40","author":"E Hemaspaandra","year":"2006","unstructured":"Hemaspaandra, E., Rothe, J., Spakowski, H.: Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP. R.A.I.R.O. Theoretical Informatics and Applications 40(1), 75\u201391 (2006)","journal-title":"R.A.I.R.O. Theoretical Informatics and Applications"},{"key":"9461_CR19","doi-asserted-by":"publisher","unstructured":"Karp, R. Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) : Complexity of Computer Computations, pp 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9461_CR20","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1051\/ita\/1987210404191","volume":"21","author":"J Ko\u0307bler","year":"1987","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Wagner, K.: The difference and truth-table hierarchies for NP. R.A.I.R.O. Informatique th\u00e9orique et Applications 21, 419\u2013435 (1987)","journal-title":"Informatique th\u00e9orique et Applications"},{"key":"9461_CR21","doi-asserted-by":"publisher","unstructured":"Meyer, A., Stockmeyer, L.: The equivalence problem for regular expressions with squaring requires exponential space. In: Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pages 125\u2013129. IEEE Computer Society Press (1972)","DOI":"10.1109\/SWAT.1972.29"},{"issue":"2","key":"9461_CR22","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/s10458-013-9224-2","volume":"28","author":"N Nguyen","year":"2014","unstructured":"Nguyen, N., Nguyen, T., Roos, M., Rothe, J.: Computational complexity and approximability of social welfare optimization in multiagent resource allocation. Journal of Autonomous Agents and Multi-Agent Systems 28(2), 256\u2013289 (2014)","journal-title":"Journal of Autonomous Agents and Multi-Agent Systems"},{"issue":"2","key":"9461_CR23","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C Papadimitriou","year":"1984","unstructured":"Papadimitriou, C., Yannakakis, M.: The complexity of facets (and some facets of complexity). J. Comput. Syst. Sci. 28(2), 244\u2013259 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"9461_CR24","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Zachos, S.: Two remarks on the power of counting. In: Proceedings of the 6th GI Conference on Theoretical Computer Science, pages 269\u2013276. Springer-Verlag Lecture Notes in Computer Science #145 (1983)","DOI":"10.1007\/BFb0036487"},{"key":"9461_CR25","doi-asserted-by":"publisher","unstructured":"Peleg, B., Sudh\u00f6lter, P.: Introduction to the theory of cooperative games. Kluwer Academic Publishers (2003)","DOI":"10.1007\/978-1-4615-0308-8"},{"key":"9461_CR26","unstructured":"Reisch, Y., Rothe, J., Schend, L.: The margin of victory in Schulze, cup, and Copeland elections: Complexity of the regular and exact variants. In: Proceedings of the 7th European Starting AI Researcher Symposium, pp 250\u2013259. IOS Press, August (2014)"},{"issue":"5","key":"9461_CR27","first-page":"551","volume":"12","author":"T Riege","year":"2006","unstructured":"Riege, T., Rothe, J.: Completeness in the boolean hierarchy: Exact-Four-Colorability, minimal graph uncolorability, and exact domatic number problems \u2013 a survey. Journal of Universal Computer Science 12(5), 551\u2013578 (2006)","journal-title":"Journal of Universal Computer Science"},{"issue":"4","key":"9461_CR28","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00224-002-1093-z","volume":"36","author":"J Rothe","year":"2003","unstructured":"Rothe, J., Spakowski, H., Vogel, J.: Exact complexity of the winner problem for Young elections. Theory of Computing Systems 36(4), 375\u2013386 (2003)","journal-title":"Theory of Computing Systems"},{"issue":"3","key":"9461_CR29","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/582475.582484","volume":"33","author":"M Schaefer","year":"2002","unstructured":"Schaefer, M., Umans, C.: Completeness in the polynomial-time hierarchy: Part I: A compendium. SIGACT News 33(3), 32\u201349 (2002a)","journal-title":"SIGACT News"},{"issue":"4","key":"9461_CR30","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/601819.601829","volume":"33","author":"M Schaefer","year":"2002","unstructured":"Schaefer, M., Umans, C.: Completeness in the polynomial-time hierarchy: Part II. SIGACT News 33(4), 22\u201336 (2002b)","journal-title":"SIGACT News"},{"issue":"1","key":"9461_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L Stockmeyer","year":"1976","unstructured":"Stockmeyer, L.: The polynomial-time hierarchy. Theor. Comput. Sci. 3(1), 1\u201322 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9461_CR32","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.orl.2006.03.011","volume":"35","author":"S Sung","year":"2006","unstructured":"Sung, S., Dimitrov, D.: On core membership testing for hedonic coalition formation games. Oper. Res. Lett. 35(2), 155\u2013158 (2006)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"9461_CR33","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1016\/j.ejor.2009.09.004","volume":"203","author":"S Sung","year":"2010","unstructured":"Sung, S., Dimitrov, D.: Computational complexity in additive hedonic games. Eur. J. Oper. Res. 203(3), 635\u2013639 (2010)","journal-title":"Eur. J. Oper. Res."},{"key":"9461_CR34","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K Wagner","year":"1987","unstructured":"Wagner, K.: More complicated questions about maxima and minima, and some closures of NP. Theor. Comput. Sci. 51, 53\u201380 (1987)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9461_CR35","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1137\/0219058","volume":"19","author":"K Wagner","year":"1990","unstructured":"Wagner, K.: Bounded query classes. SIAM J. Comput. 19(5), 833\u2013846 (1990)","journal-title":"SIAM J. Comput."},{"key":"9461_CR36","doi-asserted-by":"publisher","unstructured":"Woeginger, G.: Core stability in hedonic coalition formation. In: Proceedings of the 39th Conference on Current Trends in Theory and Practice of Computer Science, pages 33\u201350. Springer-Verlag Lecture Notes in Computer Science #7741 (January 2013a)","DOI":"10.1007\/978-3-642-35843-2_4"},{"issue":"2","key":"9461_CR37","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.mathsocsci.2012.10.001","volume":"65","author":"G Woeginger","year":"2013","unstructured":"Woeginger, G.: A hardness result for core stability in additive hedonic games. Math. Soc. Sci. 65(2), 101\u2013104 (2013b)","journal-title":"Math. Soc. Sci."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-015-9461-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-015-9461-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-015-9461-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T05:38:03Z","timestamp":1748410683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-015-9461-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,2]]},"references-count":37,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["9461"],"URL":"https:\/\/doi.org\/10.1007\/s10472-015-9461-y","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,2]]}}}