{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T19:50:48Z","timestamp":1672602648408},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p> In earlier versions of the community discovering problem, the overlap between communities was restricted by a simple count upper-bound. In this paper, we introduce the [Formula: see text]-Packing with [Formula: see text]-Overlap problem to allow for more complex constraints in the overlap region than those previously studied. Let [Formula: see text] be all possible subsets of vertices of [Formula: see text] each of size at most [Formula: see text], and [Formula: see text] be a function. The [Formula: see text]-Packing with [Formula: see text]-Overlap problem seeks at least [Formula: see text] induced subgraphs in a graph [Formula: see text] subject to: (i) each subgraph has at most [Formula: see text] vertices and obeys a property [Formula: see text], and (ii) for any pair [Formula: see text], with [Formula: see text], [Formula: see text] (i.e., the pair [Formula: see text] does not conflict). We also consider a variant that arises in clustering applications: each subgraph of a solution must contain a set of vertices from a given collection of sets [Formula: see text], and no pair of subgraphs may share vertices from the sets of [Formula: see text]. In addition, we propose similar formulations for packing hypergraphs. We give an [Formula: see text] algorithm for our problems where [Formula: see text] is the parameter and [Formula: see text] and [Formula: see text] are constants, provided that: (i) [Formula: see text] is computable in polynomial time in [Formula: see text] and (ii) the function [Formula: see text] satisfies specific conditions. Specifically, [Formula: see text] is hereditary, applicable only to overlapping subgraphs, and computable in polynomial time in [Formula: see text] and [Formula: see text]. Motivated by practical applications we give several examples of [Formula: see text] functions which meet those conditions. <\/jats:p>","DOI":"10.1142\/s0129054118500053","type":"journal-article","created":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T02:20:23Z","timestamp":1521512423000},"page":"101-122","source":"Crossref","is-referenced-by-count":1,"title":["Arbitrary Overlap Constraints in Graph Packing Problems"],"prefix":"10.1142","volume":"29","author":[{"given":"Alejandro","family":"L\u00f3pez-Ortiz","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada"}]},{"given":"Cynthia B.","family":"Perez","sequence":"additional","affiliation":[{"name":"Departamento de Computaci\u00f3n y Dise\u00f1o, Instituto Tecnol\u00f3gico de Sonora, 5 de Febrero 818 Sur, Col. Centro, Ciudad Obreg\u00f3n, Sonora, M\u00e9xico"}]},{"given":"Jazm\u00edn","family":"Romero","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada"}]}],"member":"219","published-online":{"date-parts":[[2018,3,19]]},"reference":[{"key":"S0129054118500053BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.04.020"},{"key":"S0129054118500053BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.11.008"},{"key":"S0129054118500053BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2010.05.046"},{"key":"S0129054118500053BIB006","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"S0129054118500053BIB007","doi-asserted-by":"publisher","DOI":"10.1002\/sam.10133"},{"key":"S0129054118500053BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2016.06.082"},{"issue":"3","key":"S0129054118500053BIB012","volume":"7","author":"Fernau H.","year":"2015","journal-title":"ACM Trans. Comput. Th."},{"key":"S0129054118500053BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"S0129054118500053BIB014","doi-asserted-by":"publisher","DOI":"10.1086\/229972"},{"key":"S0129054118500053BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2012.09.046"},{"key":"S0129054118500053BIB020","doi-asserted-by":"publisher","DOI":"10.1504\/IJSCCPS.2011.044171"},{"key":"S0129054118500053BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.physa.2013.07.066"},{"key":"S0129054118500053BIB022","doi-asserted-by":"publisher","DOI":"10.1504\/IJWBC.2013.054909"},{"key":"S0129054118500053BIB023","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00335"},{"key":"S0129054118500053BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-00110-4"},{"key":"S0129054118500053BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77004-6_5"},{"key":"S0129054118500053BIB027","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-09259-1_8"},{"key":"S0129054118500053BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.009"},{"key":"S0129054118500053BIB029","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"S0129054118500053BIB030","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2014.05.019"},{"issue":"10","key":"S0129054118500053BIB032","first-page":"998","volume":"8","author":"Wang M.","year":"2015","journal-title":"PVLDB"},{"key":"S0129054118500053BIB033","doi-asserted-by":"publisher","DOI":"10.1145\/2501654.2501657"},{"key":"S0129054118500053BIB034","doi-asserted-by":"publisher","DOI":"10.1145\/2594454"},{"key":"S0129054118500053BIB035","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.32"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118500053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:00:55Z","timestamp":1565092855000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118500053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":24,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2018,3,19]]},"published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1142\/S0129054118500053"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118500053","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}