{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:30Z","timestamp":1759638030558},"reference-count":16,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1981,2,1]],"date-time":"1981-02-01T00:00:00Z","timestamp":349833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":11854,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[1981,2]]},"DOI":"10.1016\/0022-0000(81)90022-2","type":"journal-article","created":{"date-parts":[[2003,12,4]],"date-time":"2003-12-04T12:01:00Z","timestamp":1070539260000},"page":"60-97","source":"Crossref","is-referenced-by-count":16,"title":["On minimal augmentation of a graph to obtain an interval graph"],"prefix":"10.1016","volume":"22","author":[{"given":"Tatsuo","family":"Ohtsuki","sequence":"first","affiliation":[]},{"given":"Hajimu","family":"Mori","sequence":"additional","affiliation":[]},{"given":"Toshinobu","family":"Kashiwabara","sequence":"additional","affiliation":[]},{"given":"Toshio","family":"Fujisawa","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0022-0000(81)90022-2_BIB1","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/0022-0000(81)90022-2_BIB2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","article-title":"Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms","volume":"13","author":"Booth","year":"1976","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0022-0000(81)90022-2_BIB3","series-title":"Proceedings","first-page":"172","article-title":"An efficient algorithm of finding a minimal triangulation of a graph","author":"Fujisawa","year":"1974"},{"key":"10.1016\/0022-0000(81)90022-2_BIB4","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","article-title":"Incidence matrices and interval graphs","volume":"15","author":"Fulkerson","year":"1965","journal-title":"Pacific J. Math."},{"key":"10.1016\/0022-0000(81)90022-2_BIB5","series-title":"Computers & Intractability: A Guide to the Theory of NP Completeness","author":"Garey","year":"1978"},{"key":"10.1016\/0022-0000(81)90022-2_BIB6","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","article-title":"A characterization of comparability graphs and of interval graphs","volume":"16","author":"Gilmore","year":"1964","journal-title":"Canad. J. Math."},{"key":"10.1016\/0022-0000(81)90022-2_BIB7","series-title":"Proceedings, 8th Design Automation Workshop","first-page":"155","article-title":"Wire routing by optimizing channel assignment within large apertures","author":"Hashimoto","year":"1971"},{"key":"10.1016\/0022-0000(81)90022-2_BIB8","series-title":"Proceedings","first-page":"657","article-title":"NP-completeness of the problem of finding a minimum-cliquenumber interval graph containing a given graph as a subgraph","author":"Kashiwabara","year":"1979"},{"key":"10.1016\/0022-0000(81)90022-2_BIB9","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","article-title":"Representation of a finite graph by a set of intervals on the real line","volume":"51","author":"Lekkerkerker","year":"1962","journal-title":"Fund. Math."},{"key":"10.1016\/0022-0000(81)90022-2_BIB10","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1137\/0205012","article-title":"A fast algorithm for finding an optimal ordering for vertex elimination on a graph","volume":"5","author":"Ohtsuki","year":"1966","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(81)90022-2_BIB11","doi-asserted-by":"crossref","first-page":"622","DOI":"10.1016\/0022-247X(76)90182-7","article-title":"Minimal triangulation of a graph and optimal pivoting order in a sparse matrix","volume":"54","author":"Ohtsuki","year":"1976","journal-title":"J. Math. Anal. Appl."},{"key":"10.1016\/0022-0000(81)90022-2_BIB12","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1109\/TCS.1979.1084695","article-title":"One-dimensional logic gate assignment and interval graphs","volume":"26","author":"Ohtsuki","year":"1979","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"10.1016\/0022-0000(81)90022-2_BIB13","series-title":"Combinatorial Algorithms: Theory and Practice","author":"Reingold","year":"1977"},{"key":"10.1016\/0022-0000(81)90022-2_BIB14","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","article-title":"Triangulated graphs and the elimination process","volume":"32","author":"Rose","year":"1970","journal-title":"J. Math. Anal. Appl."},{"key":"10.1016\/0022-0000(81)90022-2_BIB15","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","article-title":"Algorithmic aspects of vertex elimination on graphs","volume":"5","author":"Rose","year":"1976","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0022-0000(81)90022-2_BIB16","series-title":"Proceedings, 12th Design Automation Conf.","first-page":"384","article-title":"A heuristic procedure for ordering MOS arrays","author":"Yoshizawa","year":"1975"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0022000081900222?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0022000081900222?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T13:29:45Z","timestamp":1550323785000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0022000081900222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981,2]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1981,2]]}},"alternative-id":["0022000081900222"],"URL":"https:\/\/doi.org\/10.1016\/0022-0000(81)90022-2","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[1981,2]]}}}