{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T08:51:29Z","timestamp":1648543889876},"reference-count":24,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p> Consider a graph D and a family FI of connected edge subgraphs of D. Let GI(V, F) be the intersection graph of FI and G the overlap graph of FI. We describe polynomial time algorithms for subgraph overlap graphs G when their intersection graphs GI have specific hereditary properties. The algorithms are to find maximum induced complete bipartite subgraphs, maximum weight holes of a given parity, minimum dominating holes, antiholes of a given parity and some others. In addition, we define the family of subgraph filament graphs based on D, FI and GI, and prove it to be the same as the family of subgraph overlap graphs. <\/jats:p>","DOI":"10.1142\/s1793830914500189","type":"journal-article","created":{"date-parts":[[2014,1,17]],"date-time":"2014-01-17T03:38:38Z","timestamp":1389929918000},"page":"1450018","source":"Crossref","is-referenced-by-count":4,"title":["ALGORITHMS ON SUBGRAPH OVERLAP GRAPHS"],"prefix":"10.1142","volume":"06","author":[{"given":"FANICA","family":"GAVRIL","sequence":"first","affiliation":[{"name":"Computer Science Department, Technion, Haifa 32000, Israel"}]}],"member":"219","published-online":{"date-parts":[[2014,3,19]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00086-7"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190206"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2003.05.001"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0649-5"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00418-3"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.07.004"},{"key":"rf8","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90094-X"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00136-2"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00025-9"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00222-8"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.08.006"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02029-2_3"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.02.005"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.08.001"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90019-5"},{"key":"rf18","first-page":"357","volume":"390","author":"Holm L.","journal-title":"Biochem. Biophys. Res. Commun."},{"key":"rf19","first-page":"299","volume":"163","author":"Kratochvil J.","journal-title":"Discrete Math."},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-109"},{"key":"rf21","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational Molecular Biology: An Algorithmic Approach","author":"Pevsner P. A.","year":"2000"},{"key":"rf22","volume-title":"Discrete Mathematical Models with Applications to Social, Biological and Environmental Problems","author":"Roberts F. S.","year":"1976"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2032324100"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1042\/bst0311491"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-1-7"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830914500189","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:44:18Z","timestamp":1565192658000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830914500189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,19]]},"references-count":24,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2014,3,19]]},"published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.1142\/S1793830914500189"],"URL":"https:\/\/doi.org\/10.1142\/s1793830914500189","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,3,19]]}}}