{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:33:43Z","timestamp":1753882423766,"version":"3.41.2"},"reference-count":28,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:p> Let [Formula: see text] be a family of graphs and let [Formula: see text] be a set of connected graphs, each with at most [Formula: see text] vertices, [Formula: see text] fixed. A [Formula: see text]-packing of a graph GA is a vertex induced subgraph of GA with every connected component isomorphic to a member of [Formula: see text]. A maximum weight [Formula: see text]-covering of a graph GA by [Formula: see text]-packings, is a maximum weight subgraph of GA exactly covered by [Formula: see text] vertex disjoint [Formula: see text]-packings. For a graph [Formula: see text] let [Formula: see text](GA) be a graph, every vertex [Formula: see text] of which corresponds to a vertex subgraph [Formula: see text] of GA isomorphic to a member of [Formula: see text], two vertices [Formula: see text] of [Formula: see text](GA) being adjacent if and only if [Formula: see text] and [Formula: see text] have common vertices or interconnecting edges. The closed neighborhoods containment graph [Formula: see text] of a graph [Formula: see text], is the graph with vertex set [Formula: see text] and edges directed from vertices [Formula: see text] to [Formula: see text] if and only if they are adjacent in GA and the closed neighborhood of [Formula: see text] is contained in the closed neighborhood of [Formula: see text]. A graph [Formula: see text] is a [Formula: see text] reduced graph if it can be obtained from a graph [Formula: see text] by deleting the edges of a transitive subgraph [Formula: see text] of CNCG(GA). We describe 1.582-approximation algorithms for maximum weight [Formula: see text]-coverings by [Formula: see text]-packings of [Formula: see text] and [Formula: see text] reduced graphs when [Formula: see text] is vertex hereditary, has an algorithm for maximum weight independent set and [Formula: see text]. These algorithms can be applied to families of interval filament, subtree filament, weakly chordal, AT-free and circle graphs, to find 1.582 approximate maximum weight [Formula: see text]-coverings by vertex disjoint induced matchings, dissociation sets, forests whose subtrees have at most [Formula: see text] vertices, etc. <\/jats:p>","DOI":"10.1142\/s1793830921500993","type":"journal-article","created":{"date-parts":[[2021,2,5]],"date-time":"2021-02-05T03:18:57Z","timestamp":1612495137000},"source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for maximum weight <i>k<\/i>-coverings of graphs by packings"],"prefix":"10.1142","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9584-2232","authenticated-orcid":false,"given":"Fanica","family":"Gavril","sequence":"first","affiliation":[{"name":"Computer Science Department, Technion, Haifa, Israel"}]},{"given":"Mordechai","family":"Shalom","sequence":"additional","affiliation":[{"name":"TelHai Academic College, Upper Galilee, Israel"}]},{"given":"Shmuel","family":"Zaks","sequence":"additional","affiliation":[{"name":"Computer Science Department, Technion Haifa, Israel"},{"name":"ORT Braude, Academic College of Engineering, Karmiel, Israel"}]}],"member":"219","published-online":{"date-parts":[[2021,3,22]]},"reference":[{"key":"S1793830921500993BIB001","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx783"},{"key":"S1793830921500993BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301420"},{"key":"S1793830921500993BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2003.05.001"},{"key":"S1793830921500993BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.05.031"},{"key":"S1793830921500993BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0649-5"},{"key":"S1793830921500993BIB006","doi-asserted-by":"publisher","DOI":"10.1109\/TBME.2014.2375360"},{"key":"S1793830921500993BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00013-3"},{"key":"S1793830921500993BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"S1793830921500993BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00136-2"},{"key":"S1793830921500993BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00025-9"},{"key":"S1793830921500993BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00222-8"},{"key":"S1793830921500993BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.08.006"},{"key":"S1793830921500993BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02029-2_3"},{"key":"S1793830921500993BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.02.005"},{"key":"S1793830921500993BIB015","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830914500189"},{"key":"S1793830921500993BIB016","first-page":"17","volume":"35","author":"Gavril F.","year":"2015","journal-title":"J. Discrete Math."},{"key":"S1793830921500993BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.08.007"},{"key":"S1793830921500993BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00371-8"},{"key":"S1793830921500993BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-005-2452-3"},{"key":"S1793830921500993BIB020","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6750(199809)45:6<615::AID-NAV5>3.0.CO;2-5"},{"key":"S1793830921500993BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.03.003"},{"key":"S1793830921500993BIB022","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00344-5"},{"key":"S1793830921500993BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"S1793830921500993BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31265-6_26"},{"key":"S1793830921500993BIB025","doi-asserted-by":"publisher","DOI":"10.1042\/bst0311491"},{"key":"S1793830921500993BIB026","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1090\/dimacs\/046\/02","volume":"46","author":"Wan P. J.","year":"1998","journal-title":"Multichannel Optical Networks Theory and Practice 1998: DIMACS Series in Disc. Math. and Theoretical Computer Sc."},{"key":"S1793830921500993BIB027","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-60033-8_51"},{"key":"S1793830921500993BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90107-4"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830921500993","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,16]],"date-time":"2022-02-16T10:18:08Z","timestamp":1645006688000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830921500993"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,22]]},"references-count":28,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["10.1142\/S1793830921500993"],"URL":"https:\/\/doi.org\/10.1142\/s1793830921500993","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2021,3,22]]},"article-number":"2150099"}}