{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:54Z","timestamp":1759638414384},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p> We deal with a very general problem: a given graph G is to be \"packed\" into a host graph H, and we are asked about some natural optimization questions concerning this packing. The problem has never been investigated before in this general form. The input of the problem is a simple graph G = (V, E) with lower and upper bounds on its edges and weights on its vertices. The vertices correspond to items which have to be packed into the vertices (bins) of a host graph, such that each host vertex can accommodate at most L weight in total, and if two items are adjacent in G, then the distance of their host vertices in H must be between the lower and upper bounds of the edge joining the two items. Special cases are bin packing with conflicts, chromatic number, and many more. We give some general structure statements, treat some special cases, and investigate the performance guarantee of polynomial-time algorithms both in the offline and online setting. <\/jats:p>","DOI":"10.1142\/s012905411100915x","type":"journal-article","created":{"date-parts":[[2012,1,10]],"date-time":"2012-01-10T07:46:00Z","timestamp":1326181560000},"page":"1971-1993","source":"Crossref","is-referenced-by-count":5,"title":["THE GRAPH-BIN PACKING PROBLEM"],"prefix":"10.1142","volume":"22","author":[{"given":"CSILLA","family":"BUJT\u00c1S","sequence":"first","affiliation":[{"name":"Department of Computer Science and Systems Technology, University of Pannonia, Veszpr\u00e9m, Egyetem u. 10, H-8200, Hungary"}]},{"given":"GY\u00d6RGY","family":"D\u00d3SA","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Pannonia, Veszpr\u00e9m, Egyetem u. 10, H-8200, Hungary"}]},{"given":"CSAN\u00c1D","family":"IMREH","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Szeged, Szeged, \u00c1rp\u00e1d t\u00e9r 2, H-6720, Hungary"}]},{"given":"JUDIT","family":"NAGY-GY\u00d6RGY","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Szeged, Szeged, Aradi v\u00e9rtan\u00fak tere 1, H-6720, Hungary"}]},{"given":"ZSOLT","family":"TUZA","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Systems Technology, University of Pannonia, Hungary"},{"name":"Computer and Automation Institute, Hungarian Academy of Sciences, H-1111 Budapest, Kende u. 13\u201317, Hungary"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90009-4"},{"key":"rf2","first-page":"77","volume":"33","author":"Chartrand G.","journal-title":"Bull. Inst. Combin. Appl."},{"key":"rf3","unstructured":"E. G.\u00a0Coffman, J.\u00a0Csirik and G. J.\u00a0Woeginger, Handbook of Applied Optimization, eds. P.\u00a0Pardalos and M.\u00a0Resende (Oxford University Press, New York, 2002)\u00a0pp. 607\u2013615."},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1137\/060666329"},{"key":"rf5","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"Garey M. R.","year":"1979"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1137\/0405048"},{"key":"rf7","first-page":"325","volume":"21","author":"Gr\u00f6tschel M.","journal-title":"Annals of Discrete Math."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120212"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"rf10","first-page":"85","volume":"32","author":"Jansen K.","journal-title":"Information and Computation"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO;2-S"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(02)00821-X"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(03)00236-X"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90061-G"},{"key":"rf16","first-page":"42","volume":"24","author":"Whitesides S.","journal-title":"Austral. Comput. J."},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00217-X"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411100915X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:13:31Z","timestamp":1565115211000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411100915X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":18,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1142\/S012905411100915X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411100915x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]}}}