{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T05:10:02Z","timestamp":1774415402515,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540739487","type":"print"},{"value":"9783540739517","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73951-7_43","type":"book-chapter","created":{"date-parts":[[2007,8,20]],"date-time":"2007-08-20T10:18:03Z","timestamp":1187605083000},"page":"495-506","source":"Crossref","is-referenced-by-count":13,"title":["An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Yang","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Songjian","family":"Lu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"Boykov, Y., Veksler, O., Zabih, R.: Markov random fields with efficient approximations. In: Proc. IEEE Conference on Computer Vision and Pattern Recognition, pp. 648\u2013655 (1998)","DOI":"10.1109\/CVPR.1998.698673"},{"key":"43_CR2","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1006\/jcss.1999.1687","volume":"60","author":"G. Calinescu","year":"2000","unstructured":"Calinescu, G., Karloff, H., Rabani, Y.: An improved approximation algorithm for multiway cut. Journal of Computer and System Science\u00a060, 564\u2013574 (2000)","journal-title":"Journal of Computer and System Science"},{"key":"43_CR3","unstructured":"Chartrand, G., Lesniak, L.: Graphs & Digraphs, 2nd edn. The Wadsworth & Brooks\/Cole Mathematics Series (1986)"},{"key":"43_CR4","doi-asserted-by":"crossref","unstructured":"Cong, J., Labio, W., Shivakumar, N.: Multi-way VLSI circuit partitioning based on dual net representation. In: Proc. IEEE International Conference on Computer-Aided Design, pp. 56\u201362 (1994)","DOI":"10.1109\/ICCAD.1994.629744"},{"key":"43_CR5","doi-asserted-by":"crossref","unstructured":"Cunningham, W.: The optimal multiterminal cut problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 5 (1991)","DOI":"10.1090\/dimacs\/005\/07"},{"key":"43_CR6","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E. Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput.\u00a023, 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"43_CR7","volume-title":"Monograph in computer science","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. In: Monograph in computer science, Springer, Heidelberg (1999)"},{"key":"43_CR8","volume-title":"Flows in Networks","author":"L. Ford Jr.","year":"1962","unstructured":"Ford Jr., L., Fulkerson, D.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"key":"43_CR9","doi-asserted-by":"crossref","unstructured":"Karger, D., Klein, P., Stein, C., Thorup, M., Young, N.: Rounding algorithms for a geometric embedding of minimum multiway cut. In: Proc. on 31th Annual ACM Syposium on Theory of Computing, pp. 668\u2013678 (1999)","DOI":"10.1145\/301250.301430"},{"key":"43_CR10","doi-asserted-by":"crossref","unstructured":"Karger, D., Levine, M.: Finding maximum flows in undirected graphs seems easier than bipartite matching. In: Proc. on 30th Annual ACM Syposium on Theory of Computing, pp. 69\u201378 (1998)","DOI":"10.1145\/276698.276714"},{"key":"43_CR11","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"},{"key":"43_CR12","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/S009753979732147X","volume":"31","author":"J. Naor","year":"2001","unstructured":"Naor, J., Zosin, L.: A 2-approximation algorithm for the directed multiway cut problem. SIAM J. Comput.\u00a031, 477\u2013482 (2001)","journal-title":"SIAM J. Comput."},{"key":"43_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1109\/TSE.1977.233840","volume":"3","author":"H. Stone","year":"1977","unstructured":"Stone, H.: Multiprocessor scheduling with the aid of network flow algorithms. IEEE Transactions on Software Engineering\u00a03, 85\u201393 (1977)","journal-title":"IEEE Transactions on Software Engineering"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73951-7_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T13:34:57Z","timestamp":1737380097000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73951-7_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540739487","9783540739517"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73951-7_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[]}}