{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:41:51Z","timestamp":1725514911101},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540723967"},{"type":"electronic","value":"9783540723974"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-72397-4_5","type":"book-chapter","created":{"date-parts":[[2007,6,22]],"date-time":"2007-06-22T19:56:32Z","timestamp":1182542192000},"page":"59-70","source":"Crossref","is-referenced-by-count":11,"title":["The \u201cNot-Too-Heavy Spanning Tree\u201d Constraint"],"prefix":"10.1007","author":[{"given":"Gr\u00e9goire","family":"Dooms","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Irit","family":"Katriel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"5_CR1","unstructured":"Aron, I.D., Van Hentenryck, P.: A constraint satisfaction approach to the robust spanning tree problem with interval data. In: UAI, pp. 18\u201325 (2002)"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Azevedo, F.: Cardinal: A finite sets constraint solver. Constraints, 12(1), to appear (2007)","DOI":"10.1007\/s10601-006-9012-6"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/11493853_7","volume-title":"Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"N. Beldiceanu","year":"2005","unstructured":"Beldiceanu, N., Flener, P., Lorca, X.: The tree constraint. In: Bart\u00e1k, R., Milano, M. (eds.) CPAIOR 2005. LNCS, vol.\u00a03524, pp. 64\u201378. Springer, Heidelberg (2005)"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/11757375_5","volume-title":"Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"N. Beldiceanu","year":"2006","unstructured":"Beldiceanu, N., Katriel, I., Lorca, X.: Undirected forest constraints. In: Beck, J.C., Smith, B.M. (eds.) CPAIOR 2006. LNCS, vol.\u00a03990, pp. 29\u201343. Springer, Heidelberg (2006)"},{"key":"5_CR5","unstructured":"Cambazard, H., Bourreau, E.: Conception d\u2019une contrainte globale de chemin. In: 10e Journ. nat. sur la r\u00e9solution pratique de probl\u00e8mes NP-complets (JNPC\u201904), pp. 107\u2013121 (2004)"},{"key":"5_CR6","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1023\/B:ANOR.0000032577.81139.84","volume":"130","author":"A. Chabrier","year":"2004","unstructured":"Chabrier, A., Danna, E., Le Pape, C., Perron, L.: Solving a network design problem. Annals of Operations Research\u00a0130, 217\u2013239 (2004)","journal-title":"Annals of Operations Research"},{"key":"5_CR7","volume-title":"Introduction to algorithms","author":"T.T. Cormen","year":"1990","unstructured":"Cormen, T.T., Leiserson, C.E., Rivest, R.L.: Introduction to algorithms. MIT Press, Cambridge (1990)"},{"issue":"6","key":"5_CR8","doi-asserted-by":"publisher","first-page":"1184","DOI":"10.1137\/0221070","volume":"21","author":"B. Dixon","year":"1992","unstructured":"Dixon, B., Rauch, M., Tarjan, R.E.: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM Journal on Computing\u00a021(6), 1184\u20131192 (1992)","journal-title":"SIAM Journal on Computing"},{"key":"5_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/11564751_18","volume-title":"Principles and Practice of Constraint Programming - CP 2005","author":"G. Dooms","year":"2005","unstructured":"Dooms, G., Deville, Y., Dupont, P.E.: CP(Graph): Introducing a graph computation domain in constraint programming. In: van Beek, P. (ed.) CP 2005. LNCS, vol.\u00a03709, pp. 211\u2013225. Springer, Heidelberg (2005)"},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/11889205_13","volume-title":"Principles and Practice of Constraint Programming - CP 2006","author":"G. Dooms","year":"2006","unstructured":"Dooms, G., Katriel, I.: The minimum spanning tree constraint. In: Benhamou, F. (ed.) CP 2006. LNCS, vol.\u00a04204, pp. 152\u2013166. Springer, Heidelberg (2006)"},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1007\/3-540-52846-6_76","volume-title":"SWAT \u201990","author":"D. Eppstein","year":"1990","unstructured":"Eppstein, D.: Finding the k smallest spanning trees. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol.\u00a0447, pp. 38\u201347. Springer, Heidelberg (1990)"},{"issue":"3","key":"5_CR12","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1137\/S0097539700370084","volume":"32","author":"D. Eppstein","year":"2003","unstructured":"Eppstein, D.: Setting parameters by example. SIAM J. Comput.\u00a032(3), 643\u2013653 (2003)","journal-title":"SIAM J. Comput."},{"key":"5_CR13","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"key":"5_CR14","unstructured":"Gervet, C.: New structures of symbolic constraint objects: sets and graphs. In: Third Workshop on Constraint Logic Programming (WCLP\u201993), Marseille (1993)"},{"key":"5_CR15","unstructured":"Gervet, C.: Conjunto: Constraint propagation over set constraints with finite set domain variables. In: ICLP, p. 733 (1994)"},{"issue":"3","key":"5_CR16","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF00137870","volume":"1","author":"C. Gervet","year":"1997","unstructured":"Gervet, C.: Interval propagation to reason about sets: Definition and implementation of a practical language. Constraints\u00a01(3), 191\u2013244 (1997)","journal-title":"Constraints"},{"key":"5_CR17","volume-title":"AAAI","author":"C. Gervet","year":"2006","unstructured":"Gervet, C., Van Hentenryck, P.: Length-lex ordering for set csps. In: AAAI, AAAI Press, Menlo Park (2006)"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Goemans, M.X.: Minimum bounded degree spanning trees. In: FOCS \u201906: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201906), pp. 273\u2013282 (2006)","DOI":"10.1109\/FOCS.2006.48"},{"issue":"3","key":"5_CR19","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1002\/net.10069","volume":"41","author":"L. Gouveia","year":"2003","unstructured":"Gouveia, L., Magnanti, T.L.: Network flow models for designing diameter-constrained minimum-spanning and steiner trees. Networks\u00a041(3), 159\u2013173 (2003)","journal-title":"Networks"},{"key":"5_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1007\/3-540-60220-8_83","volume-title":"Algorithms and Data Structures","author":"V. King","year":"1995","unstructured":"King, V.: A simpler minimum spanning tree verification algorithm. In: Sack, J.-R., Akl, S.G., Dehne, F., Santoro, N. (eds.) WADS 1995. LNCS, vol.\u00a0955, pp. 440\u2013448. Springer, Heidelberg (1995)"},{"issue":"2","key":"5_CR21","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s00453-004-1121-2","volume":"41","author":"J. K\u00f6nemann","year":"2004","unstructured":"K\u00f6nemann, J., Levin, A., Sinha, A.: Approximating the degree-bounded minimum diameter spanning tree problem. Algorithmica\u00a041(2), 117\u2013129 (2004)","journal-title":"Algorithmica"},{"key":"5_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/3-540-46135-3_42","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"C. Pape Le","year":"2002","unstructured":"Le Pape, C., Perron, L., R\u00e9gin, J.-C., Shaw, P.: Robust and parallel solving of a network design problem. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 633\u2013648. Springer, Heidelberg (2002)"},{"key":"5_CR23","unstructured":"Puget, J.-F.: Pecos: a high level constraint programming language. In: SPICIS\u201992 (1992)"},{"key":"5_CR24","unstructured":"R\u00e9gin, J.-C.: A filtering algorithm for constraints of difference in CSPs. In: AAAI-94, pp. 362\u2013367 (1994)"},{"key":"5_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1007\/978-3-540-45193-8_47","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"M. Sellmann","year":"2003","unstructured":"Sellmann, M.: Cost-based filtering for shorter path constraints. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 694\u2013708. Springer, Heidelberg (2003)"},{"issue":"2","key":"5_CR26","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput.\u00a01(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"5_CR27","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM\u00a022(2), 215\u2013225 (1975)","journal-title":"J. ACM"},{"issue":"4","key":"5_CR28","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/322154.322161","volume":"26","author":"R.E. Tarjan","year":"1979","unstructured":"Tarjan, R.E.: Applications of path compression on balanced trees. J. ACM\u00a026(4), 690\u2013715 (1979), doi:10.1145\/322154.322161","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72397-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T11:54:45Z","timestamp":1550404485000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72397-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540723967","9783540723974"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72397-4_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}