{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:40:11Z","timestamp":1746265211485,"version":"3.40.4"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319080000"},{"type":"electronic","value":"9783319080017"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08001-7_6","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:53:00Z","timestamp":1402419180000},"page":"61-72","source":"Crossref","is-referenced-by-count":3,"title":["Approximating the Quadratic Knapsack Problem on Special Graph Classes"],"prefix":"10.1007","author":[{"given":"Ulrich","family":"Pferschy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Schauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"Alon, N., Arora, S., Manokaran, R., Moshkovitz, D., Weinstein, O.: Inapproximabilty of Densest k-Subgraph from Average Case Hardness. Technical report (2011)"},{"issue":"3","key":"6_CR2","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/0095-8956(79)90021-2","volume":"27","author":"F. Bernhart","year":"1979","unstructured":"Bernhart, F., Kainen, P.C.: The book thickness of a graph. Journal of Combinatorial Theory, Series B\u00a027(3), 320\u2013331 (1979)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-18318-8_8","volume-title":"Approximation and Online Algorithms","author":"D.Z. Chen","year":"2011","unstructured":"Chen, D.Z., Fleischer, R., Li, J.: Densest k-subgraph approximation on intersection graphs. In: Jansen, K., Solis-Oba, R. (eds.) WAOA 2010. LNCS, vol.\u00a06534, pp. 83\u201393. Springer, Heidelberg (2011)"},{"issue":"1","key":"6_CR4","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0608002","volume":"8","author":"F.R.K. Chung","year":"1987","unstructured":"Chung, F.R.K., Leighton, F.T., Rosenberg, A.L.: Embedding graphs in books: A layout problem with applications to vlsi design. SIAM Journal on Algebraic Discrete Methods\u00a08(1), 33\u201358 (1987)","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"issue":"1","key":"6_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","volume":"9","author":"D.G. Corneil","year":"1984","unstructured":"Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discrete Applied Mathematics\u00a09(1), 27\u201339 (1984)","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Kawarabayashi, K.: Algorithmic graph minor theory: Decomposition, approximation, and coloring. In: 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, pp. 637\u2013646 (2005)","DOI":"10.1109\/SFCS.2005.14"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: STOC, pp. 534\u2013543. ACM (2002)","DOI":"10.1145\/509984.509985"},{"issue":"3","key":"6_CR8","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"Feige, U., Peleg, D., Kortsarz, G.: The Dense k-Subgraph Problem. Algorithmica\u00a029(3), 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"6_CR9","unstructured":"Kainen, P.C., Overbay, S.: Book embeddings of graphs and a theorem of whitney. Technical report (2003)"},{"key":"6_CR10","first-page":"155","volume":"9","author":"J.M. Keil","year":"1991","unstructured":"Keil, J.M., Brecht, T.B.: The complexity of clustering in planar graphs. J. Combinatorial Mathematics and Combinatorial Computing\u00a09, 155\u2013159 (1991)","journal-title":"J. Combinatorial Mathematics and Combinatorial Computing"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer (2004)","DOI":"10.1007\/978-3-540-24777-7"},{"issue":"4","key":"6_CR12","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S. Khot","year":"2006","unstructured":"Khot, S.: Ruling Out PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique. SIAM J. Comput.\u00a036(4), 1025\u20131071 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"6_CR13","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1090\/S0273-0979-05-01088-8","volume":"43","author":"L. Lov\u00e1sz","year":"2006","unstructured":"Lov\u00e1sz, L.: Graph minor theory. Bulletin of the American Mathematical Society\u00a043(1), 75\u201386 (2006)","journal-title":"Bulletin of the American Mathematical Society"},{"issue":"4","key":"6_CR14","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00454-001-0047-6","volume":"26","author":"C. Moore","year":"2001","unstructured":"Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Dscrete & Computational Geometry\u00a026(4), 573\u2013590 (2001)","journal-title":"Dscrete & Computational Geometry"},{"issue":"2","key":"6_CR15","doi-asserted-by":"crossref","first-page":"121","DOI":"10.35834\/mjms\/1316092491","volume":"19","author":"S. Overbay","year":"2007","unstructured":"Overbay, S.: Graphs with small book thickness. Missouri Journal of Mathematical Sciences\u00a019(2), 121\u2013130 (2007)","journal-title":"Missouri Journal of Mathematical Sciences"},{"issue":"2","key":"6_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.7155\/jgaa.00186","volume":"13","author":"U. Pferschy","year":"2009","unstructured":"Pferschy, U., Schauer, J.: The Knapsack Problem with Conflict Graphs. Journal of Graph Algorithms and Applications\u00a013(2), 233\u2013249 (2009)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1016\/j.dam.2006.08.007","volume":"155","author":"D. Pisinger","year":"2007","unstructured":"Pisinger, D.: The quadratic knapsack problem - a survey. Discrete Applied Mathematics\u00a0155, 623\u2013648 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"6_CR18","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1287\/ijoc.1050.0172","volume":"19","author":"D. Pisinger","year":"2007","unstructured":"Pisinger, D., Rasmussen, A.B., Sandvik, R.: Solution of large quadratic knapsack problems through aggressive reduction. INFORMS Journal on Computing\u00a019, 280\u2013290 (2007)","journal-title":"INFORMS Journal on Computing"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0167-6377(02)00122-0","volume":"30","author":"D.J. Rader Jr.","year":"2002","unstructured":"Rader Jr., D.J., Woeginger, G.J.: The quadratic 0-1 knapsack problem with series-parallel support. Operations Research Letters\u00a030, 159\u2013166 (2002)","journal-title":"Operations Research Letters"},{"key":"6_CR20","first-page":"172","volume":"17","author":"P. Raghavendra","year":"2010","unstructured":"Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions Between Expansion Problems. Electronic Colloquium on Computational Complexity (ECCC)\u00a017, 172 (2010)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0012-365X(74)90042-9","volume":"7","author":"D.J. Rose","year":"1974","unstructured":"Rose, D.J.: On simple characterizations of k-trees. Discrete Mathematics\u00a07, 317\u2013322 (1974)","journal-title":"Discrete Mathematics"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Four pages are necessary and sufficient for planar graphs. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC 1986, New York, NY, USA, pp. 104\u2013108. ACM (1986)","DOI":"10.1145\/12130.12141"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08001-7_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:05:20Z","timestamp":1746263120000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08001-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319080000","9783319080017"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08001-7_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}