{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T00:25:12Z","timestamp":1725582312665},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642208768"},{"type":"electronic","value":"9783642208775"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-20877-5_20","type":"book-chapter","created":{"date-parts":[[2011,4,27]],"date-time":"2011-04-27T06:35:17Z","timestamp":1303886117000},"page":"184-194","source":"Crossref","is-referenced-by-count":2,"title":["How to Cut a Graph into Many Pieces"],"prefix":"10.1007","author":[{"given":"Ruben","family":"van der Zwaan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Berger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Grigoriev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","first-page":"293","volume-title":"Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing","author":"N. Alon","year":"1990","unstructured":"Alon, N., Seymour, P.D., Thomas, R.: A separator theorem for graphs with an excluded minor and its applications. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 293\u2013299. ACM, New York (1990)"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Karger, D., Karpinski, M.: Polynomial time approximation schemes for dense instances of np-hard problems. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 284\u2013293 (1995)","DOI":"10.1145\/225058.225140"},{"issue":"1","key":"20_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM\u00a041(1), 153\u2013180 (1994)","journal-title":"Journal of the ACM"},{"key":"20_CR4","unstructured":"Barefoot, C., Entringer, R., Swart, H.: Integrity of trees and the diameter of a graphs. Congressus Numerantium\u00a0(58), 103\u2013114 (1987)"},{"key":"20_CR5","unstructured":"Barefoot, C., Entringer, R., Swart, H.: Vulnerability in graphs:a comparative survey. Journal of Combinatorial Mathematics and Combinatorial Computing\u00a0(1), 12\u201322 (1987)"},{"issue":"1-2","key":"20_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H. Bodlaender","year":"1998","unstructured":"Bodlaender, H.: A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science\u00a0209(1-2), 1\u201345 (1998)","journal-title":"Theoretical Computer Science"},{"key":"20_CR7","unstructured":"Bodlaender, H., Hendriks, A., Grigoriev, A., Grigorieva, N.: The valve location problem in simple network topologies. INFORMS Journal on Computing (to appear)"},{"issue":"6","key":"20_CR8","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"20_CR9","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. Journal of Computer and System Sciences\u00a013(3), 335\u2013379 (1976)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"20_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9130-6","volume":"55","author":"J. Chen","year":"2009","unstructured":"Chen, J., Liu, Y., Lu, S.: An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem. Algorithmica\u00a055(1), 1\u201313 (2009)","journal-title":"Algorithmica"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.ejor.2003.10.037","volume":"162","author":"M. Costa","year":"2005","unstructured":"Costa, M., L\u00e9tocart, L., Roupin, F.: Minimal multicut and maximal integer multiflow: A survey. European Journal of Operational Research\u00a0162, 55\u201369 (2005)","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"20_CR12","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0196-6774(03)00073-7","volume":"48","author":"G. C\u0103linescu","year":"2003","unstructured":"C\u0103linescu, G., Fernandes, C., Reed, B.: Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. Journal of Algorithms\u00a048(4), 333\u2013359 (2003)","journal-title":"Journal of Algorithms"},{"issue":"3","key":"20_CR13","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G. C\u0103linescu","year":"2000","unstructured":"C\u0103linescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for multiway cut. Journal of Computer and System Sciences\u00a060(3), 564\u2013574 (2000)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM Journal on Computing\u00a023, 864\u2013894 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Feige, U., Mahdian, M.: Finding small balanced separators. In: Kleinberg, J. (ed.) Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC, Seattle, WA, USA, May 21-23, pp. 375\u2013384 (2006)","DOI":"10.1145\/1132516.1132573"},{"key":"20_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"20_CR17","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N. Garg","year":"1997","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica\u00a018, 3\u201320 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"20_CR18","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/S0196-6774(03)00111-1","volume":"50","author":"N. Garg","year":"2004","unstructured":"Garg, N., Vazirani, V., Yannakakis, M.: Multiway cuts in node weighted graphs. Journal of Algorithms\u00a050(1), 49\u201361 (2004)","journal-title":"Journal of Algorithms"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Goldschmidt, O., Hochbaum, D.: Polynomial algorithm for the k-cut problem. In: 29th Annual Symposium on Foundations of Computer Science, pp. 24\u201326, 444\u2013451 (1988)","DOI":"10.1109\/SFCS.1988.21960"},{"issue":"2","key":"20_CR20","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1016\/j.ejor.2007.02.014","volume":"186","author":"J. Guo","year":"2008","unstructured":"Guo, J., H\u00fcffner, F., Kenar, E., Niedermeier, R., Uhlmann, J.: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs. European Journal of Operational Research\u00a0186(2), 542\u2013555 (2008)","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"20_CR21","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1007\/s004530010013","volume":"27","author":"N. Guttmann-Beck","year":"2000","unstructured":"Guttmann-Beck, N., Hassin, R.: Approximation algorithms for minimum -cut. Algorithmica\u00a027(2), 198\u2013207 (2000)","journal-title":"Algorithmica"},{"issue":"7","key":"20_CR22","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1016\/S0195-6698(03)00080-5","volume":"24","author":"M.T. Hajiaghayi","year":"2003","unstructured":"Hajiaghayi, M.T., Hajiaghayi, M.: A note on the bounded fragmentation property and its applications in network reliability. European Journal of Combinatorics\u00a024(7), 891\u2013896 (2003)","journal-title":"European Journal of Combinatorics"},{"issue":"4","key":"20_CR23","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM\u00a021(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"20_CR24","unstructured":"Kann, V., Khanna, S., Lagergren, J., Panconesi, A.: On the hardness of approximating max k-cut and its dual. Chicago Journal of Theoretical Computer Science - CJTCS-1997-2 (1997)"},{"issue":"4","key":"20_CR25","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539705447037","volume":"36","author":"S. Khot","year":"2006","unstructured":"Khot, S.: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM Journal on Computing\u00a036(4), 1025\u20131071 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"20_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth, Computations and Approximations. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"20_CR27","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D. Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theoretical Computer Science\u00a0351, 394\u2013406 (2006)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"20_CR28","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043(3), 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"20_CR29","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1137\/S0097539792251730","volume":"24","author":"H. Saran","year":"1995","unstructured":"Saran, H., Vazirani, V.: Finding k cuts within twice the optimal. SIAM Journal on Computing\u00a024(1), 101\u2013108 (1995)","journal-title":"SIAM Journal on Computing"},{"issue":"7","key":"20_CR30","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s00224-009-9215-5","volume":"46","author":"M. Xiao","year":"2010","unstructured":"Xiao, M.: Simple and Improved Parameterized Algorithms for Multiterminal Cuts. Theory of Computing Systems\u00a046(7), 723\u2013736 (2010)","journal-title":"Theory of Computing Systems"},{"key":"20_CR31","first-page":"681","volume-title":"Proceedings of the Thirty-Eight Annual ACM Symposium on Theory of Computing","author":"D. Zuckerman","year":"2006","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Kleinberg, J.M. (ed.) Proceedings of the Thirty-Eight Annual ACM Symposium on Theory of Computing, pp. 681\u2013690. ACM, New York (2006)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20877-5_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T05:20:36Z","timestamp":1558588836000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20877-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642208768","9783642208775"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20877-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}