{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:50:25Z","timestamp":1759063825564},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540850960"},{"type":"electronic","value":"9783540850977"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85097-7_15","type":"book-chapter","created":{"date-parts":[[2008,8,19]],"date-time":"2008-08-19T07:18:26Z","timestamp":1219130306000},"page":"160-170","source":"Crossref","is-referenced-by-count":3,"title":["Simplicial Powers of Graphs"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Brandst\u00e4dt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Van Bang","family":"Le","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0012-365X(94)00052-K","volume":"145","author":"H.-J. Bandelt","year":"1995","unstructured":"Bandelt, H.-J., Henkmann, A., Nicolai, F.: Powers of distance-hereditary graphs. Discrete Math.\u00a0145, 37\u201360 (1995)","journal-title":"Discrete Math."},{"key":"15_CR2","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/0095-8956(91)90004-4","volume":"51","author":"H.-J. Bandelt","year":"1991","unstructured":"Bandelt, H.-J., Prisner, E.: Clique graphs and Helly graphs. J. Combin. Th.\u00a0(B) 51, 34\u201345 (1991)","journal-title":"J. Combin. Th. (B)"},{"key":"15_CR3","volume-title":"Trees and proximity representations","author":"J.P. Barth\u00e9l\u00e9my","year":"1991","unstructured":"Barth\u00e9l\u00e9my, J.P., Gu\u00e9noche, A.: Trees and proximity representations. Wiley & Sons, Chichester (1991)"},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/0166-218X(93)90165-K","volume":"43","author":"E. Bibelnieks","year":"1993","unstructured":"Bibelnieks, E., Dearing, P.M.: Neighborhood subtree tolerance graphs. Discrete Applied Math.\u00a043, 13\u201326 (1993)","journal-title":"Discrete Applied Math."},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0895480193253415","volume":"11","author":"A. Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Chepoi, V.D., Voloshin, V.I.: Dually chordal graphs. SIAM J. Discrete Math.\u00a011, 437\u2013455 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Hundt, C.: Ptolemaic graphs and interval graphs are leaf powers; extended abstract. In: Proceedings of LATIN 2008. LNCS, vol.\u00a04957, pp. 479\u2013491 (2008)","DOI":"10.1007\/978-3-540-78773-0_42"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.ipl.2006.01.004","volume":"98","author":"A. Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Le, V.B.: Structure and linear time recognition of 3-leaf powers. Information Processing Letters\u00a098, 133\u2013138 (2006)","journal-title":"Information Processing Letters"},{"key":"15_CR8","unstructured":"Brandst\u00e4dt, A., Le, V.B., Rautenbach, D.: Exact leaf powers (submitted)"},{"key":"15_CR9","unstructured":"Brandst\u00e4dt, A., Le, V.B., Rautenbach, D.: Distance-hereditary 5-leaf powers (submitted)"},{"key":"15_CR10","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a03. SIAM, Philadelphia (1999)"},{"key":"15_CR11","unstructured":"Brandst\u00e4dt, A., Le, V.B., Sritharan, R.: Structure and linear time recognition of 4-leaf powers. ACM Transactions on Algorithms(accepted)"},{"key":"15_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/978-3-540-74456-6_47","volume-title":"Mathematical Foundations of Computer Science 2007","author":"A. Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt, A., Wagner, P.: On (k,\u2113)-leaf powers; extended abstract. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol.\u00a04708, pp. 525\u2013535. Springer, Heidelberg (2007) (Full version submitted)"},{"key":"15_CR13","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/0095-8956(74)90047-1","volume":"1","author":"P. Buneman","year":"1974","unstructured":"Buneman, P.: A note on the metric properties of trees. J. Combin. Th.\u00a0 (B) 1, 48\u201350 (1974)","journal-title":"J. Combin. Th."},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.disc.2005.03.020","volume":"293","author":"J. C\u00e1ceres","year":"2005","unstructured":"C\u00e1ceres, J., M\u00e1rquez, A., Oellermann, O.R., Puertas, M.L.: Rebuilding convex sets in graphs. Discrete Math.\u00a0293, 26\u201337 (2005)","journal-title":"Discrete Math."},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Chang, M.-S., Ko, T.: The 3-Steiner Root Problem; extended abstract. In: Proceedings 33rd International Workshop on Graph-Theoretic Concepts in Computer Science WG 2007. LNCS, vol.\u00a04769, pp. 109\u2013120 (2007)","DOI":"10.1007\/978-3-540-74839-7_11"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539701389154","volume":"32","author":"Z.-Z. Chen","year":"2003","unstructured":"Chen, Z.-Z., Jiang, T., Lin, G.: Computing phylogenetic roots with bounded degrees and errors. SIAM J. Computing\u00a032, 864\u2013879 (2003)","journal-title":"SIAM J. Computing"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/3-540-58715-2_123","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E.: Efficient parallel and linear time sequential split decomposition. In: Thiagarajan, P.S. (ed.) FSTTCS 1994. LNCS, vol.\u00a0880, pp. 171\u2013180. Springer, Heidelberg (1994)"},{"key":"15_CR18","first-page":"23","volume":"24B","author":"E. Dahlhaus","year":"1987","unstructured":"Dahlhaus, E., Duchet, P.: On strongly chordal graphs. Ars Combinatoria\u00a024B, 23\u201330 (1987)","journal-title":"Ars Combinatoria"},{"key":"15_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/978-3-540-30551-4_35","volume-title":"Algorithms and Computation","author":"M. Dom","year":"2004","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R.: Error compensation in leaf root problems; extended abstract. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 389\u2013401. Springer, Heidelberg (2004); Algorithmica 44, 363\u2013381 (2006)"},{"key":"15_CR20","first-page":"67","volume":"21","author":"P. Duchet","year":"1984","unstructured":"Duchet, P.: Classical perfect graphs. Annals of Discrete Math.\u00a021, 67\u201396 (1984)","journal-title":"Annals of Discrete Math."},{"key":"15_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0012-365X(83)90154-1","volume":"43","author":"M. Farber","year":"1983","unstructured":"Farber, M.: Characterizations of strongly chordal graphs. Discrete Math.\u00a043, 173\u2013189 (1983)","journal-title":"Discrete Math."},{"key":"15_CR22","volume-title":"Computers and Intractability\u2013A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability\u2013A Guide to the Theory of NP-Completeness. Freeman, New York (1979) (twenty-third printing 2002)"},{"key":"15_CR23","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0166-218X(01)00207-4","volume":"121","author":"R.B. Hayward","year":"2002","unstructured":"Hayward, R.B., Kearney, P.E., Malton, A.: NeST graphs. Discrete Applied Math.\u00a0121, 139\u2013153 (2002)","journal-title":"Discrete Applied Math."},{"key":"15_CR24","volume-title":"Graph Theory","author":"F. Harary","year":"1972","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Massachusetts (1972)"},{"issue":"28","key":"15_CR25","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1093\/qmath\/28.4.417","volume":"2","author":"E. Howorka","year":"1977","unstructured":"Howorka, E.: A characterization of distance-hereditary graphs. Quart. J. Math. Oxford, Ser.\u00a02(28), 417\u2013420 (1977)","journal-title":"Quart. J. Math. Oxford, Ser."},{"key":"15_CR26","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0095-8956(79)90069-8","volume":"27","author":"E. Howorka","year":"1979","unstructured":"Howorka, E.: On metric properties of certain clique graphs. J. Combin. Th.\u00a0(B) 27, 67\u201374 (1979)","journal-title":"J. Combin. Th."},{"key":"15_CR27","unstructured":"Kennedy, W.: Strictly chordal graphs and phylogenetic roots, Master Thesis, University of Alberta (2005)"},{"key":"15_CR28","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.jda.2005.06.005","volume":"4","author":"W. Kennedy","year":"2006","unstructured":"Kennedy, W., Lin, G., Yan, G.: Strictly chordal graphs are leaf powers. Journal of Discrete Algorithms\u00a04, 511\u2013525 (2006)","journal-title":"Journal of Discrete Algorithms"},{"key":"15_CR29","unstructured":"Le, V.B., Tuy, N.N.: A good characterization of squares of block graphs (manuscript, 2008)"},{"key":"15_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/3-540-40996-3_46","volume-title":"Algorithms and Computation","author":"G.-H. Lin","year":"2000","unstructured":"Lin, G.-H., Kearney, P.E., Jiang, T.: Phylogenetic k-root and Steiner k-root. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol.\u00a01969, pp. 539\u2013551. Springer, Heidelberg (2000)"},{"key":"15_CR31","unstructured":"Lubiw, A.: \u0393-free matrices, Master of Science Thesis, Dept. of Combin. and Optim., University of Waterloo (1982)"},{"key":"15_CR32","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1137\/0216057","volume":"16","author":"A. Lubiw","year":"1987","unstructured":"Lubiw, A.: Doubly lexical orderings of matrices. SIAM J. Computing\u00a016, 854\u2013879 (1987)","journal-title":"SIAM J. Computing"},{"key":"15_CR33","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1195","volume":"42","author":"N. Nishimura","year":"2002","unstructured":"Nishimura, N., Ragde, P., Thilikos, D.: On graph powers for leaf-labeled trees. J. Algorithms\u00a042, 69\u2013108 (2002)","journal-title":"J. Algorithms"},{"key":"15_CR34","doi-asserted-by":"publisher","first-page":"1456","DOI":"10.1016\/j.disc.2006.03.030","volume":"306","author":"D. Rautenbach","year":"2006","unstructured":"Rautenbach, D.: Some remarks about leaf roots. Discrete Math.\u00a0306, 1456\u20131461 (2006)","journal-title":"Discrete Math."},{"key":"15_CR35","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85097-7_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T10:59:19Z","timestamp":1709204359000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85097-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540850960","9783540850977"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85097-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}