{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T11:50:55Z","timestamp":1712749855350},"reference-count":9,"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":[[2003,2]]},"abstract":" In [7] was introduced a new decomposition scheme for bipartite graphs that was called canonical decomposition. Weak-bisplit graphs are totally decomposable following this decomposition. We give here linear time algorithms for the recognition of weak-bisplit graphs as well as for two subclasses of this class, the P6<\/jats:sub>-free bipartite graphs and the bi-cographs. Our algorithms extends the technics developped in [2] for cographs's recognition. We conclude by presenting efficient solutions for some optimization problems when dealing with weak-bisplit graphs. <\/jats:p>","DOI":"10.1142\/s0129054103001625","type":"journal-article","created":{"date-parts":[[2003,6,25]],"date-time":"2003-06-25T00:53:09Z","timestamp":1056502389000},"page":"107-136","source":"Crossref","is-referenced-by-count":10,"title":["LINEAR TIME RECOGNITION AND OPTIMIZATIONS FOR WEAK-BISPLIT GRAPHS, BI-COGRAPHS AND BIPARTITE P6<\/sub>-FREE GRAPHS"],"prefix":"10.1142","volume":"14","author":[{"given":"V.","family":"GIAKOUMAKIS","sequence":"first","affiliation":[{"name":"La.R.I.A, Universit\u00e9 de Picardie Jules Verne, 5 rue du Moulin Neuf, 80000 Amiens, France"}]},{"given":"J. M.","family":"VANHERPE","sequence":"additional","affiliation":[{"name":"Structures Discr\u00e8tes et Algorithmes, Universit\u00e9 du Maine, avenue O. Messian, 72085 Le Mans, C\u00e9dex 9, France"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90023-P"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1137\/0214065"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90004-G"},{"key":"rf4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/10692760_1","volume":"1517","author":"Courcelle B.","year":"1998"},{"key":"rf7","first-page":"513","volume":"10","author":"Fouquet J. L.","journal-title":"International Journal of Fundations of Computer Science"},{"key":"rf8","series-title":"Mathematical series","volume-title":"Computers and Intractability: A guide to the Theory of NP-Completeness","author":"Garey M. G.","year":"1979"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1996.0519"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020209"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579333"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054103001625","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:26:40Z","timestamp":1565191600000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103001625"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,2]]},"references-count":9,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,2]]}},"alternative-id":["10.1142\/S0129054103001625"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103001625","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,2]]}}}