{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T18:51:44Z","timestamp":1694631104923},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2008,2,15]],"date-time":"2008-02-15T00:00:00Z","timestamp":1203033600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,2,15]],"date-time":"2008-02-15T00:00:00Z","timestamp":1203033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2008,12]]},"DOI":"10.1007\/s10601-007-9040-x","type":"journal-article","created":{"date-parts":[[2008,2,14]],"date-time":"2008-02-14T22:12:17Z","timestamp":1203027137000},"page":"459-489","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Combining Tree Partitioning, Precedence, and Incomparability Constraints"],"prefix":"10.1007","volume":"13","author":[{"given":"Nicolas","family":"Beldiceanu","sequence":"first","affiliation":[]},{"given":"Pierre","family":"Flener","sequence":"additional","affiliation":[]},{"given":"Xavier","family":"Lorca","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,2,15]]},"reference":[{"issue":"3","key":"9040_CR1","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A. Aho","year":"1981","unstructured":"Aho, A., Sagiv, Y., Szymanski, T., & Ullman, J. D. (1981). Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM Journal of Computing, 10(3), 405\u2013421.","journal-title":"SIAM Journal of Computing"},{"key":"9040_CR2","unstructured":"Beldiceanu, N., Carlsson, M., & Rampon, J.-X. (2005). Global constraint catalog. Research Report T2005-08, Swedish Institute of Computer Science."},{"key":"9040_CR3","doi-asserted-by":"crossref","unstructured":"Beldiceanu, N., Flener, P., & Lorca, X. (2005). The tree constraint. In Proceedings of CP-AI-OR\n                           \u201905, LNCS (Vol. 3524, pp. 64\u201378). Springer.","DOI":"10.1007\/11493853_7"},{"key":"9040_CR4","unstructured":"Beldiceanu, N., Flener, P., & Lorca, X. (2006). Combining tree partitioning, precedence, incomparability, and degree constraints, with an application to phylogenetic and ordered-path problems. Technical Report 2006-020, Department of Information Technology, Uppsala University, Sweden. Available at http:\/\/www.it.uu.se\/research\/publications\/reports\/2006-020\/."},{"key":"9040_CR5","unstructured":"Beldiceanu, N., Flener, P., & Lorca, X. (2006). Partitionnement de graphes par des arbres sous contraintes de degr\u00e9. In Deuxi\u00e8mes Journ\u00e9es Francophones de Programmation par Contraintes (JFPC\u201906) (pp. 35\u201342). (in French)."},{"key":"9040_CR6","doi-asserted-by":"crossref","unstructured":"Beldiceanu, N., & Lorca, X. (2007). Necessary condition for path partitioning constraints. In Proceedings of CP-AI-OR\u201907, LNCS (Vol. 4510, pp. 141\u2013154). Springer.","DOI":"10.1007\/978-3-540-72397-4_11"},{"key":"9040_CR7","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1146\/annurev.ecolsys.33.010802.150511","volume":"33","author":"O. Bininda-Emonds","year":"2002","unstructured":"Bininda-Emonds, O., Gittleman, J., & Steel, M. (2002). The (super)tree of life: Procedures, problems, and prospects. Annual Reviews of Ecological Systems, 33, 265\u2013289.","journal-title":"Annual Reviews of Ecological Systems"},{"key":"9040_CR8","unstructured":"Bodirsky, M., Duchier, D., Miehle, S., & Niehren, J. (2004). A new algorithm for normal dominance constraints. In Proceedings of SODA\u201904, (pp. 59\u201367)."},{"key":"9040_CR9","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.artint.2006.12.004","volume":"171","author":"M. Bodirsky","year":"2007","unstructured":"Bodirsky, M., & Kutz, M. (2007). Determining the consistency of partial tree descriptions. Artificial Intelligence, 171, 185\u2013196.","journal-title":"Artificial Intelligence"},{"key":"9040_CR10","unstructured":"Bourreau, E. (1999). Traitement de contraintes sur les graphes en programmation par contraintes. Ph.D. thesis, University of Paris 13, France (March). In French."},{"key":"9040_CR11","unstructured":"Cambazard, H., & Bourreau, E. (2004). Conception d\u2019une contrainte globale de chemin. In Proceedings of the Dixi\u00e8mes Journ\u00e9es Nationales sur la R\u00e9solution Pratique de Probl\u00e8mes NP-Complets (JNPC\u201904) (pp. 107\u2013120). (in French)."},{"key":"9040_CR12","first-page":"376","volume":"23","author":"A. Cayley","year":"1889","unstructured":"Cayley, A. (1889). A theorem on trees. Quarterly Journal of Mathematics, 23, 376\u2013378.","journal-title":"Quarterly Journal of Mathematics"},{"issue":"4","key":"9040_CR13","first-page":"1","volume":"31","author":"K. Cooper","year":"2001","unstructured":"Cooper, K., Harvey, T., & Kennedy, K. (2001). A simple, fast dominance algorithm. Software Practice and Experience, 31(4), 1\u201310.","journal-title":"Software Practice and Experience"},{"key":"9040_CR14","unstructured":"COSYTEC. (1997). CHIP Reference Manual, release 5.1 edition."},{"key":"9040_CR15","doi-asserted-by":"crossref","unstructured":"Dooms, G., Deville, Y., & Dupont, P. E. (2005). CP(Graph): Introducing a graph computation domain in constraint programming. In Proceedings of CP\u201905, LNCS (Vol. 3709, pp. 211\u2013225).","DOI":"10.1007\/11564751_18"},{"key":"9040_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1978","unstructured":"Garey, M. R., & Johnson, D. S. (1978). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York."},{"key":"9040_CR17","doi-asserted-by":"crossref","unstructured":"Gent, I., Prosser, P., Smith, B., & Wei, W. (2003). Supertree construction with constraint programming. In Proceedings of CP\u201903, LNCS (Vol. 2833, pp. 837\u2013841).","DOI":"10.1007\/978-3-540-45193-8_63"},{"key":"9040_CR18","doi-asserted-by":"crossref","unstructured":"Katriel, I. (2006). Expected-case analysis for delayed filtering. In Proceedings of CP-AI-OR\u201906, LNCS (Vol. 3990, pp. 119\u2013125). Springer-Verlag.","DOI":"10.1007\/11757375_11"},{"key":"9040_CR19","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1093\/auk\/119.1.88","volume":"119","author":"M. Kennedy","year":"2002","unstructured":"Kennedy, M., & Page, R. D. (2002). Seabird supertrees: Combining partial estimates of procellariiform phylogeny. The Auk, A Quarterly Journal of Ornithology, 119, 88\u2013108.","journal-title":"The Auk, A Quarterly Journal of Ornithology"},{"key":"9040_CR20","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0012-365X(83)90021-3","volume":"43","author":"J. Koml\u00f3s","year":"1983","unstructured":"Koml\u00f3s, J., & Szemer\u00e9di, E. (1983). Limit distribution for the existence of a Hamilton cycle in a random graph. Discrete Mathematics, 43, 55\u201363.","journal-title":"Discrete Mathematics"},{"issue":"1","key":"9040_CR21","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/357062.357071","volume":"1","author":"T. Lengauer","year":"1979","unstructured":"Lengauer, T., & Tarjan, R. E. (1979). A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems, 1(1), 121\u2013141.","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"9040_CR22","unstructured":"Lorca, X. (2007). Contraintes de Partitionnement de Graphe. Ph.D. thesis, Universit\u00e9 de Nantes, \u00c9cole des Mines, Nantes, France (in French)."},{"key":"9040_CR23","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0166-218X(95)00074-2","volume":"69","author":"M. Ng","year":"1996","unstructured":"Ng, M., & Wormald, N. (1996). Reconstruction of rooted trees from subtrees. Discrete Applied Mathematics, 69, 19\u201331.","journal-title":"Discrete Applied Mathematics"},{"key":"9040_CR24","doi-asserted-by":"crossref","unstructured":"Pape, C. L., Perron, L., R\u00e9gin, J.-C., & Shaw, P. (2002). Robust and parallel solving of a network design problem. In Proceedings of CP\u201902, LNCS (Vol. 2470, pp. 633\u2013648). Springer-Verlag.","DOI":"10.1007\/3-540-46135-3_42"},{"key":"9040_CR25","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0012-365X(76)90068-6","volume":"14","author":"L. P\u00f3sa","year":"1976","unstructured":"P\u00f3sa, L. (1976). Hamiltonian circuits in random graphs. Discrete Mathematics, 14, 359\u2013364.","journal-title":"Discrete Mathematics"},{"key":"9040_CR26","unstructured":"Quesada, L. (2006). Solving Constrained Graph Problems Using Reachability Constraints Based on Transitive Closure and Dominators. Ph.D. thesis, Universit\u00e9 catholique de Louvain, Louvain-la-Neuve, Belgium."},{"key":"9040_CR27","unstructured":"R\u00e9gin, J.-C. (1994). A filtering algorithm for constraints of difference in CSP. In Proceedings of AAAI\u201994 (pp. 362\u2013367)."},{"key":"9040_CR28","unstructured":"R\u00e9gin, J.-C. (1996). Generalized arc consistency for global cardinality constraint. In Proceedings of AAAI\u201996 (pp. 209\u2013215)."},{"key":"9040_CR29","unstructured":"Richaud, G., Lorca, X., & Jussien, N. (2007). A portable and efficient implementation of global constraints: The tree constraint case. In Abreu, S. & Costa, V. S. (eds.), Proceedings of CICLOPS\u201907, Porto, Portugal (September)."},{"key":"9040_CR30","unstructured":"Schulte, C., Lagerkvist, M., & Tack, G. (2006). Gecode. Available at http:\/\/www.gecode.org\/."},{"key":"9040_CR31","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M. Steel","year":"1992","unstructured":"Steel, M. (1992). The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification, 9, 91\u2013116.","journal-title":"Journal of Classification"},{"key":"9040_CR32","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1112\/jlms\/s1-21.2.98","volume":"21","author":"W. T. Tutte","year":"1946","unstructured":"Tutte, W. T. (1946). On Hamiltonian circuits. Journal of the London Mathematical Society, 21, 98\u2013101.","journal-title":"Journal of the London Mathematical Society"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-007-9040-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-007-9040-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-007-9040-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-007-9040-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T00:34:51Z","timestamp":1652661291000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-007-9040-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2,15]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["9040"],"URL":"https:\/\/doi.org\/10.1007\/s10601-007-9040-x","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2,15]]},"assertion":[{"value":"14 June 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 December 2007","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2008","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}