{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T11:50:22Z","timestamp":1712749822862},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1999,12]]},"abstract":" We describe here a technique of decomposition of bipartite graphs which seems to be as interesting within this context as the well known modular and split techniques for the decomposition of general graphs. In particular, we characterize by forbidden subgraphs the family of bipartite graphs which are totally decomposable (i.e. reducible to single vertices) with respect to our decomposition. This family contains previously known families of graphs such as bicographs and P6<\/jats:sub>-free bipartite graphs. As an application we provide polynomial solutions of optimization problems, some of them being NP-complete for general bipartite graphs. <\/jats:p>","DOI":"10.1142\/s0129054199000368","type":"journal-article","created":{"date-parts":[[2002,7,28]],"date-time":"2002-07-28T19:09:56Z","timestamp":1027883396000},"page":"513-533","source":"Crossref","is-referenced-by-count":32,"title":["BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION"],"prefix":"10.1142","volume":"10","author":[{"given":"JEAN-LUC","family":"FOUQUET","sequence":"first","affiliation":[{"name":"IUT Mesures Physiques, Universit\u00e9 du Maine, Avenue O. Messiaen, Le Mans, 72085 Cedex 9, France"}]},{"given":"VASSILIS","family":"GIAKOUMAKIS","sequence":"additional","affiliation":[{"name":"L.a.R.I.A., Universit\u00e9 de Picardie Jules Verne, 5 Rue du Moulin Neuf, Amiens, 80000, France"}]},{"given":"JEAN-MARIE","family":"VANHERPE","sequence":"additional","affiliation":[{"name":"L.a.R.I.A., Universit\u00e9 de Picardie Jules Verne, 5 Rue du Moulin Neuf, Amiens, 80000, France"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.43.9.842"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90023-P"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1137\/0214065"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90004-G"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1007\/10692760_1"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1137\/0603021"},{"key":"p_17","first-page":"283","volume":"29","author":"Frost H.","year":"1990","journal-title":"ARS Combinatoria"},{"key":"p_19","first-page":"389","volume":"18","author":"Giakoumakis V.","year":"1997","journal-title":"Bi-Complement Appl.Math."},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579333"},{"key":"p_21","first-page":"739","volume":"23","author":"Harary F.","year":"1982","journal-title":"Comment. Math. Univ. Carolinae"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00173-2"},{"key":"p_25","first-page":"261","volume":"60","author":"McKee T.A.","year":"1987","journal-title":"Congressus Numerantium"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054199000368","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:34:43Z","timestamp":1565138083000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054199000368"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,12]]},"references-count":12,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[1999,12]]}},"alternative-id":["10.1142\/S0129054199000368"],"URL":"https:\/\/doi.org\/10.1142\/s0129054199000368","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,12]]}}}