{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T15:43:08Z","timestamp":1777563788948,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,1,25]],"date-time":"2017-01-25T00:00:00Z","timestamp":1485302400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["MI439\/14-1"],"award-info":[{"award-number":["MI439\/14-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s10878-017-0111-7","type":"journal-article","created":{"date-parts":[[2017,1,25]],"date-time":"2017-01-25T04:24:39Z","timestamp":1485318279000},"page":"591-616","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions"],"prefix":"10.1007","volume":"36","author":[{"given":"Marc","family":"Hellmuth","sequence":"first","affiliation":[]},{"given":"Nicolas","family":"Wieseke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,1,25]]},"reference":[{"key":"111_CR1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0012-365X(97)84217-3","volume":"165166","author":"D Achlioptas","year":"1997","unstructured":"Achlioptas D (1997) The complexity of g-free colourability. Discrete Math 165166:21\u201330 (Graphs and combinatorics)","journal-title":"Discrete Math"},{"key":"111_CR2","unstructured":"Bernini A, Ferrari L, Pinzani R (2009) Enumeration of some classes of words avoiding two generalized patterns of length three. J Autom Lang Comb 14(2):129\u2013147"},{"key":"111_CR3","unstructured":"Bilotta S, Grazzini E, Pergola E (2013) Counting binary words avoiding alternating patterns. J Integer Seq 16:Article 13.4.8"},{"key":"111_CR4","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1006\/aima.1998.1743","volume":"138","author":"S B\u00f6cker","year":"1998","unstructured":"B\u00f6cker S, Dress A (1998) Recovering symbolically dated, rooted trees from symbolic ultrametrics. Adv Math 138:105\u2013125","journal-title":"Adv Math"},{"issue":"1","key":"111_CR5","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.jcta.2004.10.007","volume":"110","author":"P Br\u00e4nd\u00e9n","year":"2005","unstructured":"Br\u00e4nd\u00e9n P, Mansour T (2005) Finite automata and pattern avoidance in words. J Comb Theory Ser A 110(1):127\u2013145","journal-title":"J Comb Theory Ser A"},{"key":"111_CR6","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, Spinrad J (1999) Graph classes: a survey SIAM monographs on discrete mathematics and applications. Society of Industrial and Applied Mathematics, Philadephia"},{"issue":"2","key":"111_CR7","first-page":"1","volume":"9","author":"A Burstein","year":"2002","unstructured":"Burstein A, Mansour T (2002) Words restricted by patterns with at most 2 distinct letters. Electron J Comb Number Theory 9(2):1\u201316","journal-title":"Electron J Comb Number Theory"},{"issue":"4","key":"111_CR8","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D Corneil","year":"1985","unstructured":"Corneil D, Perl Y, Stewart L (1985) A linear recognition algorithm for cographs. SIAM J Comput 14(4):926\u2013934","journal-title":"SIAM J Comput"},{"key":"111_CR9","doi-asserted-by":"crossref","unstructured":"Corneil DG, Lerchs H, Stewart Burlingham LK (1981) Complement reducible graphs. Discrete Appl Math 3:163\u2013174","DOI":"10.1016\/0166-218X(81)90013-5"},{"issue":"1","key":"111_CR10","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1002\/jgt.21724","volume":"75","author":"P Dorbec","year":"2014","unstructured":"Dorbec P, Montassier M, Ochem P (2014) Vertex partitions of graphs into cographs and stars. J Graph Theory 75(1):75\u201390","journal-title":"J Graph Theory"},{"issue":"3","key":"111_CR11","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1109\/31.1748","volume":"35","author":"E El-Mallah","year":"1988","unstructured":"El-Mallah E, Colbourn C (1988) The complexity of some edge deletion problems. IEEE Trans Circuits Syst 35(3):354\u2013362","journal-title":"IEEE Trans Circuits Syst"},{"key":"111_CR12","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/S0168-9525(00)02005-9","volume":"16","author":"W Fitch","year":"2000","unstructured":"Fitch W (2000) Homology: a personal view on some of the problems. Trends Genet 16:227\u2013231","journal-title":"Trends Genet"},{"key":"111_CR13","doi-asserted-by":"crossref","unstructured":"Gimbel J, Nes\u011btr\u01d0l J (2002) Partitions of graphs into cographs. Electronic notes in discrete mathematics, vol 11. In: The ninth quadrennial international conference on graph theory, combinatorics, algorithms and applications, pp 705\u2013721","DOI":"10.1016\/S1571-0653(04)00115-5"},{"key":"111_CR14","doi-asserted-by":"crossref","DOI":"10.1201\/b10959","volume-title":"Handbook of product graphs","author":"R Hammack","year":"2011","unstructured":"Hammack R, Imrich W, Klav\u017ear S (2011) Handbook of product graphs, 2nd edn. CRC Press, Boca Raton","edition":"2"},{"key":"111_CR15","doi-asserted-by":"crossref","unstructured":"Hellmuth M, Hernandez-Rosales M, Huber KT, Moulton V, Stadler PF, Wieseke N (2013a) Orthology relations, symbolic ultrametrics, and cographs. J Math Biol 66(1\u20132):399\u2013420","DOI":"10.1007\/s00285-012-0525-x"},{"key":"111_CR16","doi-asserted-by":"crossref","unstructured":"Hellmuth M, Imrich W, Kupka T (2013b) Partial star products: a local covering approach for the recognition of approximate Cartesian product graphs. Math Comput Sci 7(3):255\u2013273","DOI":"10.1007\/s11786-013-0156-7"},{"key":"111_CR17","doi-asserted-by":"crossref","unstructured":"Hellmuth M, Wieseke N (2015) On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions. In: Xu D, Du D, Du D (eds) Computing and combinatorics. Lecture Notes in Computer Science, vol 9198. Springer International Publishing, Cham, pp 609\u2013623","DOI":"10.1007\/978-3-319-21398-9_48"},{"key":"111_CR18","volume-title":"From sequence data Including orthologs, paralogs, and xenologs to gene and species trees, Chap. 21","author":"M Hellmuth","year":"2016","unstructured":"Hellmuth M, Wieseke N (2016) From sequence data Including orthologs, paralogs, and xenologs to gene and species trees, Chap. 21. Springer International Publishing, Cham"},{"issue":"7","key":"111_CR19","doi-asserted-by":"crossref","first-page":"2058","DOI":"10.1073\/pnas.1412770112","volume":"112","author":"M Hellmuth","year":"2015","unstructured":"Hellmuth M, Wieseke N, Lechner M, Lenhof H, Middendorf M, Stadler P (2015) Phylogenomics with paralogs. Proc Natl Acad Sci 112(7):2058\u20132063","journal-title":"Proc Natl Acad Sci"},{"issue":"19","key":"111_CR20","doi-asserted-by":"crossref","first-page":"S6","DOI":"10.1186\/1471-2105-13-S19-S6","volume":"13","author":"M Hernandez-Rosales","year":"2012","unstructured":"Hernandez-Rosales M, Hellmuth M, Wieseke N, Huber KT, Moulton V, Stadler PF (2012) From event-labeled gene trees to species trees. BMC Bioinform 13(19):S6","journal-title":"BMC Bioinform"},{"key":"111_CR21","doi-asserted-by":"publisher","unstructured":"Lafond M, El-Mabrouk N (2014) Orthology and paralogy constraints: satisfiability and consistency. BMC Genomics 15(Suppl 6):S12. doi: 10.1186\/1471-2164-15-S6-S12 .","DOI":"10.1186\/1471-2164-15-S6-S12"},{"key":"111_CR22","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1186\/1471-2105-12-124","volume":"12","author":"M Lechner","year":"2011","unstructured":"Lechner M, Findei\u00df S, Steiner L, Marz M, Stadler PF, Prohaska SJ (2011) Proteinortho: detection of (co-)orthologs in large-scale analysis. BMC Bioinform 12:124","journal-title":"BMC Bioinform"},{"issue":"8","key":"111_CR23","doi-asserted-by":"crossref","first-page":"e105,015","DOI":"10.1371\/journal.pone.0105015","volume":"9","author":"M Lechner","year":"2014","unstructured":"Lechner M, Hernandez-Rosales M, Doerr D, Wiesecke N, Thevenin A, Stoye J, Hartmann RK, Prohaska SJ, Stadler PF (2014) Orthology detection combining clustering and synteny for very large datasets. PLoS ONE 9(8):e105,015","journal-title":"PLoS ONE"},{"key":"111_CR24","unstructured":"Lerchs H (1971a) On cliques and kernels. Technical Report, Department of Computer Science University of Toronto"},{"key":"111_CR25","unstructured":"Lerchs H (1971b) On the clique\u2013kernel structure of graphs. Technical Report, Department of Computer Science, University of Toronto"},{"key":"111_CR26","doi-asserted-by":"crossref","unstructured":"Liu Y, Wang J, Guo J, Chen J (2011) Cograph editing: complexity and parametrized algorithms. In: Fu B, Du DZ (eds) COCOON 2011, Lecture Notes in Computer Science, vol 6842. Springer, Berlin, Heidelberg, pp 110\u2013121","DOI":"10.1007\/978-3-642-22685-4_10"},{"key":"111_CR27","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/j.tcs.2011.11.040","volume":"461","author":"Y Liu","year":"2012","unstructured":"Liu Y, Wang J, Guo J, Chen J (2012) Complexity and parameterized algorithms for cograph editing. Theoret Comput Sci 461:45\u201354","journal-title":"Theoret Comput Sci"},{"issue":"3","key":"111_CR28","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0020-0190(92)90041-S","volume":"41","author":"J Misra","year":"1992","unstructured":"Misra J, Gries D (1992) A constructive proof of vizing\u2019s theorem. Inf Process Lett 41(3):131\u2013133","journal-title":"Inf Process Lett"},{"key":"111_CR29","unstructured":"Moret BM (1997) The theory of computation. Addison-Wesley Longman Publishing Co., Inc. Boston, MA"},{"key":"111_CR30","unstructured":"Pudwell L (2008a) Enumeration schemes for pattern-avoiding words and permutations. ProQuest, New Brunswick, New Jersey"},{"key":"111_CR31","unstructured":"Pudwell L (2008b) Enumeration schemes for words avoiding patterns with repeated letters. Electron. J. Comb. Number Theory 8(40):1\u201319"},{"key":"111_CR32","doi-asserted-by":"crossref","unstructured":"Schaefer T (1978) The complexity of satisfiability problems. In: Proceedings of the tenth annual ACM symposium on theory of computing, STOC \u201978. ACM, New York, NY, USA, pp 216\u2013226","DOI":"10.1145\/800133.804350"},{"key":"111_CR33","first-page":"23","volume":"3","author":"VG Vizing","year":"1964","unstructured":"Vizing VG (1964) On an estimate of the chromatic class of a p-graph. J Math Biol 3:23\u201330 (Russian)","journal-title":"J Math Biol"},{"key":"111_CR34","unstructured":"Zhang P (2014) A study on generalized solution concepts in constraint satisfaction and graph colouring. Master\u2019s thesis, University of British Columbia, Canada"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0111-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0111-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0111-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T19:40:03Z","timestamp":1568749203000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0111-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,25]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["111"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0111-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,25]]}}}