{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:33:44Z","timestamp":1725514424207},"publisher-location":"Berlin, Heidelberg","reference-count":29,"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_10","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"115-127","source":"Crossref","is-referenced-by-count":2,"title":["A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs"],"prefix":"10.1007","author":[{"given":"Shin-ichi","family":"Nakano","sequence":"first","affiliation":[]},{"given":"Ryuhei","family":"Uehara","sequence":"additional","affiliation":[]},{"given":"Takeaki","family":"Uno","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/978-3-540-39644-4_6","volume-title":"Discovery Science","author":"T. Asai","year":"2003","unstructured":"Asai, T., et al.: Discovering Frequent Substructures in Large Unordered Trees. In: Grieser, G., Tanaka, Y., Yamamoto, A. (eds.) DS 2003. LNCS (LNAI), vol.\u00a02843, pp. 47\u201361. Springer, Heidelberg (2003)"},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"H.-J. Bandelt","year":"1986","unstructured":"Bandelt, H.-J., Mulder, H.M.: Distance-Hereditary Graphs. Journal of Combinatorial Theory, Series B\u00a041, 182\u2013208 (1986)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/(SICI)1097-0037(199805)31:3<177::AID-NET4>3.0.CO;2-C","volume":"31","author":"A. Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F.F.: A Linear-Time Algorithm for Connected r-Domination and Steiner Tree on Distance-Hereditary Graphs. Networks\u00a031, 177\u2013182 (1998)","journal-title":"Networks"},{"key":"10_CR4","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"10_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/978-3-540-39890-5_11","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"A. Bretscher","year":"2003","unstructured":"Bretscher, A., et al.: A Simple Linear Time LexBFS Cograph Recognition Algorithm. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 119\u2013130. Springer, Heidelberg (2003)"},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/S0166-218X(99)00146-8","volume":"99","author":"H.J. Broersma","year":"2000","unstructured":"Broersma, H.J., Dahlhaus, E., Kloks, T.: A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs. Discrete Applied Mathematics\u00a099, 367\u2013400 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1007\/3-540-63890-3_37","volume-title":"Algorithms and Computation","author":"M.-S. Chang","year":"1997","unstructured":"Chang, M.-S., Hsieh, S.-Y., Chen, G.-H.: Dynamic Programming on Distance-Hereditary Graphs. In: Leong, H.-V., Jain, S., Imai, H. (eds.) ISAAC 1997. LNCS, vol.\u00a01350, pp. 344\u2013353. Springer, Heidelberg (1997)"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0166-218X(00)00330-9","volume":"116","author":"M.-S. Chang","year":"2002","unstructured":"Chang, M.-S., et al.: Domination in distance-hereditary graphs. Discrete Applied Mathematics\u00a0116, 103\u2013113 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR9","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D.G. Corneil","year":"2004","unstructured":"Corneil, D.G.: Lexicographic Breadth First Search \u2014 A Survey. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 1\u201319. Springer, Heidelberg (2004)"},{"issue":"4","key":"10_CR10","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D.G. Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A Linear Recognition Algorithm for Cographs. SIAM Journal on Computing\u00a014(4), 926\u2013934 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0304-3975(00)00234-6","volume":"263","author":"G. Damiand","year":"2001","unstructured":"Damiand, G., Habib, M., Paul, C.: A Simple Paradigm for Graph Recognition: Application to Cographs and Distance Hereditary Graphs. Theoretical Computer Science\u00a0263, 99\u2013111 (2001)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"10_CR12","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1137\/0217032","volume":"17","author":"A. D\u2019Atri","year":"1988","unstructured":"D\u2019Atri, A., Moscarini, M.: Distance-Hereditary Graphs, Steiner Trees, and Connected Domination. SIAM Journal on Computing\u00a017(3), 521\u2013538 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/978-3-540-27801-6_12","volume-title":"Combinatorial Pattern Matching","author":"R. Geary","year":"2004","unstructured":"Geary, R., et al.: A Simple Optimal Representation for Balanced Parentheses. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 159\u2013172. Springer, Heidelberg (2004)"},{"key":"10_CR14","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Annals of Discrete Mathematics, vol.\u00a057. Elsevier, Amsterdam (2004)","edition":"2"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","volume":"27","author":"P.L. Hammer","year":"1990","unstructured":"Hammer, P.L., Maffray, F.: Completely Separable Graphs. Discrete Applied Mathematics\u00a027, 85\u201399 (1990)","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR16","first-page":"169","volume-title":"Workshop on Knowledge Discovery in Databases","author":"L.B. Holder","year":"1994","unstructured":"Holder, L.B., Cook, D.J., Djoko, S.: Substructure Discovery in the SUBDUE System. In: Workshop on Knowledge Discovery in Databases, pp. 169\u2013180. AAAI, Menlo Park (1994)"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1093\/qmath\/28.4.417","volume":"28","author":"E. Howorka","year":"1977","unstructured":"Howorka, E.: A Characterization of Distance-Hereditary Graphs. Quart. J. Math. Oxford\u00a028, 417\u2013420 (1977)","journal-title":"Quart. J. Math. Oxford"},{"key":"10_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/3-540-45655-4_10","volume-title":"Computing and Combinatorics","author":"S.-Y. Hsieh","year":"2002","unstructured":"Hsieh, S.-Y., et al.: Efficient Algorithms for the Hamiltonian Problem on Distance-Hereditary Graphs. In: Ibarra, O.H., Zhang, L. (eds.) COCOON 2002. LNCS, vol.\u00a02387, pp. 77\u201386. Springer, Heidelberg (2002)"},{"key":"10_CR19","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-45372-5_2","volume-title":"Principles of Data Mining and Knowledge Discovery","author":"A. Inokuchi","year":"2000","unstructured":"Inokuchi, A., Washio, T., Motoda, H.: An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data. In: Zighed, A.D.A., Komorowski, J., \u017bytkow, J.M. (eds.) PKDD 2000. LNCS (LNAI), vol.\u00a01910, pp. 13\u201323. Springer, Heidelberg (2000)"},{"key":"10_CR20","series-title":"The Art of Computer Programming","volume-title":"Generating All Trees","author":"D.E. Knuth","year":"2005","unstructured":"Knuth, D.E.: Generating All Trees. The Art of Computer Programming, vol.\u00a04. Addison-Wesley, Reading (2005)"},{"key":"10_CR21","series-title":"The Art of Computer Programming","volume-title":"Sorting and Searching","author":"D.E. Knuth","year":"1998","unstructured":"Knuth, D.E.: Sorting and Searching, 2nd edn. The Art of Computer Programming, vol.\u00a03. Addison-Wesley, Reading (1998)","edition":"2"},{"key":"10_CR22","first-page":"118","volume-title":"Proc. 38th ACM Symp. on the Theory of Computing","author":"J.I. Munro","year":"1997","unstructured":"Munro, J.I., Raman, V.: Succinct Representation of Balanced Parentheses, Static Trees and Planar graphs. In: Proc. 38th ACM Symp. on the Theory of Computing, pp. 118\u2013126. ACM Press, New York (1997)"},{"key":"10_CR23","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/S0097539799364092","volume":"31","author":"J.I. Munro","year":"2001","unstructured":"Munro, J.I., Raman, V.: Succinct Representation of Balanced Parentheses and Static Trees. SIAM Journal on Computing\u00a031, 762\u2013776 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/978-3-540-30559-0_3","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Nakano","year":"2004","unstructured":"Nakano, S., Uno, T.: Constant Time Generation of Trees with Specified Diameter. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 33\u201345. Springer, Heidelberg (2004)"},{"issue":"3","key":"10_CR25","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0020-0190(02)00240-5","volume":"84","author":"S.-I. Nakano","year":"2002","unstructured":"Nakano, S.-I.: Efficient Generation of Plane Trees. Information Processing Letters\u00a084(3), 167\u2013172 (2002)","journal-title":"Information Processing Letters"},{"issue":"3","key":"10_CR26","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1002\/net.1","volume":"37","author":"F. Nicolai","year":"2001","unstructured":"Nicolai, F., Szymczak, T.: Homogeneous Sets and Domination: A Linear Time Algorithm for Distance-Hereditary Graphs. Networks\u00a037(3), 117\u2013128 (2001)","journal-title":"Networks"},{"issue":"2","key":"10_CR27","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic Aspects of Vertex Elimination on Graphs. SIAM Journal on Computing\u00a05(2), 266\u2013283 (1976)","journal-title":"SIAM Journal on Computing"},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"Spinrad, J.P.: Efficient Graph Representations. American Mathematical Society (2003)","DOI":"10.1090\/fim\/019"},{"key":"10_CR29","first-page":"71","volume-title":"8th ACM SIGKDD international conference on Knowledge discovery and data mining","author":"M.J. Zaki","year":"2002","unstructured":"Zaki, M.J.: Efficiently Mining Frequent Trees in a Forest. In: 8th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 71\u201380. ACM Press, New York (2002)"}],"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_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:38:02Z","timestamp":1619516282000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_10","relation":{},"subject":[]}}