{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T10:50:14Z","timestamp":1743072614652,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642112683"},{"type":"electronic","value":"9783642112690"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_19","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"234-245","source":"Crossref","is-referenced-by-count":3,"title":["A Probabilistic Approach to Problems Parameterized above or below Tight Bounds"],"prefix":"10.1007","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/S0196-8858(02)00007-6","volume":"29","author":"N. Alon","year":"2002","unstructured":"Alon, N.: Voting paradoxes and digraphs realizations. Advances in Applied Math.\u00a029, 126\u2013135 (2002)","journal-title":"Advances in Applied Math."},{"issue":"1","key":"19_CR2","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.jalgor.2003.09.003","volume":"50","author":"N. Alon","year":"2004","unstructured":"Alon, N., Gutin, G., Krivelevich, M.: Algorithms with large domination ratio. J. Algorithms\u00a050(1), 118\u2013131 (2004)","journal-title":"J. Algorithms"},{"key":"19_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84800-998-1","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"J. Bang-Jensen","year":"2009","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, London (2009)","edition":"2"},{"key":"19_CR4","volume-title":"Basic Linear Algebra","author":"T.S. Blyth","year":"2000","unstructured":"Blyth, T.S., Robertson, E.F.: Basic Linear Algebra. Springer, Heidelberg (2000)"},{"key":"19_CR5","unstructured":"Bourgain, J.: Walsh subspaces of $L\\sp{p}$-product spaces. In: Seminar on Functional Analysis (1979\u20131980) (French)"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0024-3795(93)90235-G","volume":"192","author":"D. Coppersmith","year":"1993","unstructured":"Coppersmith, D.: Solving linear systems over GF(2): block Lanczos algorithm. Lin. Algebra Applic.\u00a0192, 33\u201360 (1993)","journal-title":"Lin. Algebra Applic."},{"key":"19_CR7","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":"19_CR8","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"arameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: arameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol.\u00a0XIV. Springer, Heidelberg (2006)"},{"key":"19_CR9","unstructured":"Gutin, G., Kim, E.J., Mnich, M., Yeo, A.: Ordinal Embedding Relaxations Parameterized Above Tight Lower Bound. Tech. Report arXiv:0907.5427"},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00224-007-1330-6","volume":"41","author":"G. Gutin","year":"2007","unstructured":"Gutin, G., Rafiey, A., Szeider, S., Yeo, A.: The linear arrangement problem parameterized above guaranteed value. Theory Comput. Syst.\u00a041, 521\u2013538 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"19_CR11","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s00453-007-9144-0","volume":"52","author":"G. Gutin","year":"2008","unstructured":"Gutin, G., Szeider, S., Yeo, A.: Fixed-parameter complexity of minimum profile problems. Algorithmica\u00a052(2), 133\u2013152 (2008)","journal-title":"Algorithmica"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J., Venkatesh, S.: On the advantage over a random assignment. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, vol.\u00a025(2), pp. 117\u2013149 (2002)","DOI":"10.1002\/rsa.20031"},{"key":"19_CR13","first-page":"374","volume-title":"STOC 2007\u2014Proceedings of the 39th Annual ACM Symposium on Theory of Computing","author":"P. Heggernes","year":"2007","unstructured":"Heggernes, P., Paul, C., Telle, J.A., Villanger, Y.: Interval completion with few edges. In: STOC 2007\u2014Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 374\u2013381. ACM, New York (2007); Full version appeared in SIAM J. Comput. 38(5) (2008-2009)"},{"issue":"2","key":"19_CR14","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms\u00a031(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"19_CR15","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.jcss.2008.08.004","volume":"75","author":"M. Mahajan","year":"2009","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing above or below guaranteed values. J. of Computer and System Sciences\u00a075(2), 137\u2013153 (2009)","journal-title":"J. of Computer and System Sciences"},{"key":"19_CR16","series-title":"Oxford Lecture Series in Mathematics and its Applications","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 Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006)"},{"key":"19_CR17","unstructured":"Vovk, V.: Private communication (August 2009)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T20:26:30Z","timestamp":1676060790000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}