{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:55:10Z","timestamp":1762102510676,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T00:00:00Z","timestamp":1589587200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T00:00:00Z","timestamp":1589587200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972070","61772115"],"award-info":[{"award-number":["61972070","61772115"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s00453-020-00712-8","type":"journal-article","created":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T03:44:11Z","timestamp":1589600651000},"page":"3066-3090","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Characterizing Star-PCGs"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1012-2373","authenticated-orcid":false,"given":"Mingyu","family":"Xiao","sequence":"first","affiliation":[]},{"given":"Hiroshi","family":"Nagamochi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,16]]},"reference":[{"key":"712_CR1","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"S Booth","year":"1976","unstructured":"Booth, S., Lueker, S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"712_CR2","unstructured":"Brandst\u00e4dt, A.: On leaf powers. Technical report, University of Rostock (2010)"},{"issue":"7","key":"712_CR3","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1093\/comjnl\/bxs087","volume":"56","author":"T Calamoneri","year":"2013","unstructured":"Calamoneri, T., Frascaria, D., Sinaimeri, B.: All graphs with at most seven vertices are pairwise compatibility graphs. Comput. J. 56(7), 882\u2013886 (2013)","journal-title":"Comput. J."},{"issue":"11","key":"712_CR4","doi-asserted-by":"publisher","first-page":"1616","DOI":"10.1093\/comjnl\/bxt068","volume":"57","author":"T Calamoneri","year":"2014","unstructured":"Calamoneri, T., Frangioni, A., Sinaimeri, B.: Pairwise compatibility graphs of caterpillars. Comput. J. 57(11), 1616\u20131623 (2014)","journal-title":"Comput. J."},{"key":"712_CR5","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2013.12.015","volume":"524","author":"T Calamoneri","year":"2014","unstructured":"Calamoneri, T., Petreschi, R.: On pairwise compatibility graphs having Dilworth number two. Theor. Comput. Sci. 524, 34\u201340 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"712_CR6","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.tcs.2014.06.024","volume":"547","author":"T Calamoneri","year":"2014","unstructured":"Calamoneri, T., Petreschi, R.: On pairwise compatibility graphs having Dilworth number $$k$$. Theor. Comput. Sci. 547, 82\u201389 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"712_CR7","doi-asserted-by":"publisher","first-page":"360002","DOI":"10.1142\/S1793830913600021","volume":"5","author":"T Calamoneri","year":"2013","unstructured":"Calamoneri, T., Petreschi, R., Sinaimeri, B.: On the pairwise compatibility property of some superclasses of threshold graphs. Discrete Math. Algorithms Appl. 5(2), 360002 (2013)","journal-title":"Discrete Math. Algorithms Appl."},{"issue":"3","key":"712_CR8","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1137\/140978053","volume":"58","author":"T Calamoneri","year":"2016","unstructured":"Calamoneri, T., Sinaimeri, B.: Pairwise compatibility graphs: a survey. SIAM Rev. 58(3), 445\u2013460 (2016)","journal-title":"SIAM Rev."},{"key":"712_CR9","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. Comput. 32, 864\u2013879 (2003)","journal-title":"SIAM J. Comput."},{"key":"712_CR10","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.tcs.2015.01.011","volume":"571","author":"S Durocher","year":"2015","unstructured":"Durocher, S., Mondal, D., Rahman, MdS: On graphs that are not PCGs. Theor. Comput. Sci. 571, 78\u201387 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"712_CR11","doi-asserted-by":"publisher","first-page":"401","DOI":"10.2307\/2412923","volume":"27","author":"J Felsenstein","year":"1978","unstructured":"Felsenstein, J.: Cases in which parsimony or compatibility methods will be positively misleading. Syst. Zool. 27, 401\u2013410 (1978)","journal-title":"Syst. Zool."},{"issue":"3","key":"712_CR12","doi-asserted-by":"publisher","first-page":"341","DOI":"10.7155\/jgaa.00419","volume":"21","author":"MdI Hossain","year":"2017","unstructured":"Hossain, MdI, Salma, S.A., Rahman, MdS, Mondal, D.: A necessary condition and a sufficient condition for pairwise compatibility graphs. J. Graph Algorithms Appl. 21(3), 341\u2013352 (2017)","journal-title":"J. Graph Algorithms Appl."},{"key":"712_CR13","first-page":"177","volume-title":"Algorithms in Bioinformatics, LNCS 2812","author":"PE Kearney","year":"2003","unstructured":"Kearney, P.E., Munro, J.I., Phillips, D.: Efficient generation of uniform samples from phylogenetic trees. In: Benson, G., Page, R. (eds.) Algorithms in Bioinformatics, LNCS 2812, pp. 177\u2013189. Springer, Berlin (2003)"},{"key":"712_CR14","first-page":"539","volume-title":"Algorithms and Computation, LNCS 1969","author":"G Lin","year":"2000","unstructured":"Lin, G., Kearney, P.E., Jiang, T.: Phylogenetic k-root and Steiner k-root. In: Goos, G., Hartmanis, J., van Leeuwen, J., Lee, D.T., Teng, S.-H. (eds.) Algorithms and Computation, LNCS 1969, pp. 539\u2013551. Springer, Berlin (2000)"},{"key":"712_CR15","doi-asserted-by":"crossref","unstructured":"Mehnaz, S., Rahman, M.S.: Pairwise compatibility graphs revisited. In: Proceedings of the 2013 International Conference on Informatics, Electronics Vision (ICIEV), pp. 1\u20136 (2013)","DOI":"10.1109\/ICIEV.2013.6572681"},{"key":"712_CR16","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.M.: On graph powers for leaf-labeled trees. J. Algorithms 42, 69\u2013108 (2002)","journal-title":"J. Algorithms"},{"key":"712_CR17","doi-asserted-by":"publisher","first-page":"81","DOI":"10.7155\/jgaa.00286","volume":"17","author":"SA Salma","year":"2013","unstructured":"Salma, S.A., Rahman, MdS, Hossain, MdI: Triangle-free outerplanar 3-graphs are pairwise compatibility graphs. J. Graph Algorithms Appl. 17, 81\u2013102 (2013)","journal-title":"J. Graph Algorithms Appl."},{"key":"712_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2019.105875","volume":"153","author":"M Xiao","year":"2020","unstructured":"Xiao, M., Nagamochi, H.: Some reduction operations to pairwise compatibility graphs. Inf. Process. Lett. 153, 105875 (2020)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"712_CR19","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1142\/S1793830910000917","volume":"2","author":"MN Yanhaona","year":"2010","unstructured":"Yanhaona, M.N., Bayzid, MdS, Rahman, MdS: Discovering pairwise compatibility graphs. Discrete Math. Algorithm Appl. 2(4), 607\u2013624 (2010)","journal-title":"Discrete Math. Algorithm Appl."},{"key":"712_CR20","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s12190-008-0204-7","volume":"30","author":"MN Yanhaona","year":"2009","unstructured":"Yanhaona, M.N., Hossain, K.S.M.T., Rahman, MdS: Pairwise compatibility graphs. J. Appl. Math. Comput. 30, 479\u2013503 (2009)","journal-title":"J. Appl. Math. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00712-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00712-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00712-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,15]],"date-time":"2021-05-15T23:19:28Z","timestamp":1621120768000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00712-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,16]]},"references-count":20,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["712"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00712-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,5,16]]},"assertion":[{"value":"20 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}