{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:33:35Z","timestamp":1725514415923},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_6","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"67-78","source":"Crossref","is-referenced-by-count":5,"title":["A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns"],"prefix":"10.1007","author":[{"given":"Hitoshi","family":"Yamasaki","sequence":"first","affiliation":[]},{"given":"Takayoshi","family":"Shoudai","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D. Angluin","year":"1980","unstructured":"Angluin, D.: Finding patterns common to a set of strings. J. Comput. Syst. Sci.\u00a021, 46\u201362 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR2","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci.\u00a013, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR3","unstructured":"Gardi, F.: The mutual exclusion scheduling problem for proper interval graphs. LIF Research Report 02-2002, Laboratoire d\u2019Informatique Fondamentale de Marseille (April 2002)"},{"issue":"3","key":"6_CR4","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"J. Hopcroft","year":"1973","unstructured":"Hopcroft, J., Karp, R.: An n 5\/2 algorithm for maximum matching in bipartite graphs. SIAM J. Comput.\u00a02(3), 225\u2013231 (1973)","journal-title":"SIAM J. Comput."},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Horv\u00e1th, T., Ramon, J., Wrobel, S.: Frequent Subgraph Mining in Outerplanar Graphs. In: Proc. KDD 2006, pp. 197\u2013206 (2006)","DOI":"10.1145\/1150402.1150427"},{"issue":"2","key":"6_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"G.S. Lueker","year":"1979","unstructured":"Lueker, G.S., Booth, K.S.: A Linear Time Algorithm for Deciding Interval Graph Isomorphism. J. ACM\u00a026(2), 183\u2013195 (1979)","journal-title":"J. ACM"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0166-218X(98)00077-8","volume":"88","author":"F.R. McMorris","year":"1998","unstructured":"McMorris, F.R., Wang, C., Zhang, P.: On probe interval graphs. Disc. Appl. Math.\u00a088, 315\u2013324 (1998)","journal-title":"Disc. Appl. Math."},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/3-540-11980-9_19","volume-title":"RIMS Symposium on Software Science and Engineering","author":"T. Shinohara","year":"1983","unstructured":"Shinohara, T.: Polynomial time inference of extended regular pattern languages. In: Goto, E., et al. (eds.) RIMS 1982. LNCS, vol.\u00a0147, pp. 115\u2013127. Springer, Heidelberg (1983)"},{"key":"6_CR9","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-540-28633-2_24","volume-title":"PRICAI 2004: Trends in Artificial Intelligence","author":"Y. Suzuki","year":"2004","unstructured":"Suzuki, Y., et al.: Polynomial Time Inductive Inference of Ordered Tree Languages with Height-Constrained Variables from Positive Data. In: Zhang, C., W. Guesgen, H., Yeap, W.-K. (eds.) PRICAI 2004. LNCS (LNAI), vol.\u00a03157, pp. 211\u2013220. Springer, Heidelberg (2004)"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.tcs.2005.10.022","volume":"350","author":"Y. Suzuki","year":"2006","unstructured":"Suzuki, Y., et al.: Ordered Term Tree Languages Which Are Polynomial Time Inductively Inferable from Positive Data. Theor. Comput. Sci.\u00a0350, 63\u201390 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR11","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1007\/11536314_22","volume-title":"Inductive Logic Programming","author":"R. Takami","year":"2005","unstructured":"Takami, R., et al.: Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data. In: Kramer, S., Pfahringer, B. (eds.) ILP 2005. LNCS (LNAI), vol.\u00a03625, pp. 366\u2013383. Springer, Heidelberg (2005)"},{"key":"6_CR12","first-page":"309","volume":"10","author":"P. Zhang","year":"1994","unstructured":"Zhang, P., et al.: An algorithm based on graph theory for the assembly of contings in physical mapping of DNA. CABIOS\u00a010, 309\u2013317 (1994)","journal-title":"CABIOS"},{"key":"6_CR13","unstructured":"Zhang, P.: Probe Interval Graph and Its Applications to Physical Mapping of DNA. In: Int. Conf. Computational Molecular Biology, RECOMB 2000 (Poster Session) (2000)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:34:06Z","timestamp":1605764046000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_6","relation":{},"subject":[]}}