{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T05:28:23Z","timestamp":1740461303760,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_12","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"114-125","source":"Crossref","is-referenced-by-count":5,"title":["On Problem Kernels for Possible Winner Determination under the k-Approval Protocol"],"prefix":"10.1007","author":[{"given":"Nadja","family":"Betzler","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Bachrach, Y., Betzler, N., Faliszewski, P.: Probabilistic possible winner determination. In: Proc. of 24th AAAI (to appear 2010)","DOI":"10.1609\/aaai.v24i1.7609"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Baumeister, D., Rothe, J.: Taking the final step to a full dichotomy of the Possible Winner problem in pure scoring rules. In: Proc. of 19th ECAI (2010) (short paper)","DOI":"10.3233\/978-1-60750-606-5-1019"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1007\/978-3-642-03816-7_12","volume-title":"Mathematical Foundations of Computer Science 2009","author":"N. Betzler","year":"2009","unstructured":"Betzler, N., Dorn, B.: Towards a complexity dichotomy of finding possible winners in elections based on scoring rules. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 124\u2013136. Springer, Heidelberg (2009)"},{"issue":"2","key":"12_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.ic.2009.10.001","volume":"208","author":"N. Betzler","year":"2010","unstructured":"Betzler, N., Guo, J., Niedermeier, R.: Parameterized computational complexity of Dodgson and Young elections. Inform. Comput.\u00a0208(2), 165\u2013177 (2010)","journal-title":"Inform. Comput."},{"key":"12_CR5","unstructured":"Betzler, N., Hemmann, S., Niedermeier, R.: A multivariate complexity analysis of determining possible winners given incomplete votes. In: Proc. of 21st IJCAI, pp. 53\u201358 (2009)"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-642-11269-0_2","volume-title":"IWPEC 2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 17\u201337. Springer, Heidelberg (2009)"},{"issue":"8","key":"12_CR7","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. Syst. Sci.\u00a075(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-540-30559-0_22","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Chor","year":"2004","unstructured":"Chor, B., Fellows, M., Juedes, D.W.: Linear kernels in linear time, or how to save k colors in o(n 2) steps. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 257\u2013269. Springer, Heidelberg (2004)"},{"key":"12_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Automata, Languages and Programming","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 378\u2013389. Springer, Heidelberg (2009)"},{"key":"12_CR10","doi-asserted-by":"crossref","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, Heidelberg (1999)"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-642-04645-2_27","volume-title":"Algorithmic Game Theory","author":"E. Elkind","year":"2009","unstructured":"Elkind, E., Faliszewski, P., Slinko, A.: Swap bribery. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) Algorithmic Game Theory. LNCS, vol.\u00a05814, pp. 299\u2013310. Springer, Heidelberg (2009)"},{"key":"12_CR12","first-page":"133","volume-title":"Proc. of 40th STOC","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proc. of 40th STOC, pp. 133\u2013142. ACM, New York (2008)"},{"issue":"1","key":"12_CR13","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News\u00a038(1), 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"issue":"1","key":"12_CR14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.jcss.2006.09.002","volume":"73","author":"E. Hemaspaandra","year":"2007","unstructured":"Hemaspaandra, E., Hemaspaandra, L.A.: Dichotomy for voting systems. J. Comput. Syst. Sci.\u00a073(1), 73\u201383 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR15","unstructured":"Konczak, K., Lang, J.: Voting procedures with incomplete preferences. In: Proc. of IJCAI 2005 Multidisciplinary Workshop on Advances in Preference Handling (2005)"},{"key":"12_CR16","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 University Press, Oxford (2006)"},{"key":"12_CR17","unstructured":"Pini, M.S., Rossi, F., Venable, K.B., Walsh, T.: Incompleteness and incomparability in preference aggregation. In: Proc. of 20th IJCAI, pp. 1464\u20131469 (2007)"},{"key":"12_CR18","first-page":"196","volume-title":"Proc. of 23rd AAAI","author":"L. Xia","year":"2008","unstructured":"Xia, L., Conitzer, V.: Determining possible and necessary winners under common voting rules given partial orders. In: Proc. of 23rd AAAI, pp. 196\u2013201. AAAI Press, Menlo Park (2008)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T12:31:59Z","timestamp":1740400319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}