{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T16:42:05Z","timestamp":1778863325535,"version":"3.51.4"},"reference-count":33,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2003,4,1]],"date-time":"2003-04-01T00:00:00Z","timestamp":1049155200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,29]],"date-time":"2013-07-29T00:00:00Z","timestamp":1375056000000},"content-version":"vor","delay-in-days":3772,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electronic Notes in Theoretical Computer Science"],"published-print":{"date-parts":[[2003,4]]},"DOI":"10.1016\/s1571-0661(04)81014-4","type":"journal-article","created":{"date-parts":[[2004,9,29]],"date-time":"2004-09-29T16:47:47Z","timestamp":1096476467000},"page":"209-222","source":"Crossref","is-referenced-by-count":69,"special_numbering":"C","title":["Cutting Up Is Hard To Do"],"prefix":"10.1016","volume":"78","author":[{"given":"Rodney","family":"G. Downey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Estivill-Castro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Prieto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances A.","family":"Rosamund","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB1","doi-asserted-by":"crossref","unstructured":"S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 2\u201312.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB2","doi-asserted-by":"crossref","unstructured":"S. Arora, Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. Proc.38th Annual IEEE Symposium on the Foundations of Computing(FOCS'97), IEEE Press 1997, 554\u2013563.","DOI":"10.1109\/SFCS.1997.646145"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB3","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/s001530050069","article-title":"The parameterized complexity of short computation and factorization","volume":"36","author":"Liming","year":"1997","journal-title":"Archive for Mathematical Logic"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB4","unstructured":"Liming Cai, M. Fellows, D. Juedes and F. Rosamond. Efficient polynomial-time approximation schemes for problems on planar structures: upper and lower bounds. Manuscript, 2001."},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB5","unstructured":"Liming Cai and D. Juedes. Subexponential parameterized algorithms collapse the W-hierarchy Proceeding of ICALP 2001, Crete, Greece, Springer-Verlag LNCS 2076 2001."},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB6","doi-asserted-by":"crossref","unstructured":"J. Chen, I.A. Kanj and W. Jia. vertex cover:further observations and further improvements. Proceedings of the 25th International Workshop on Graph-Theortic Concepts in Computer Science, (WG'99), Lecture Notes in Computer Science 1665 (1999), 313\u2013324.","DOI":"10.1007\/3-540-46784-X_30"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB7","author":"Dehne","year":"2002","journal-title":"Private communication"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB8","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","article-title":"Fixed-parameter tractability and completeness I:basic theory","volume":"24","author":"Downey","year":"1995","journal-title":"SIAM Journal of Computing"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB9","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","article-title":"Fixed-parameter tractability and completeness II:completeness for W[1]","volume":"141","author":"Downey","year":"1995","journal-title":"Theoretical Computer Science A"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB10","series-title":"Parameterized Complexity","author":"Downey","year":"1998"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB11","unstructured":"R. Downey, M. Fellows, E. Prieto-Rodriguez and F. Rosamond. Fixed-Parameter tractability and completeness V:parametric miniatures. Manuscript in preparation, 2002."},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB12","first-page":"545","volume":"29","author":"Downey","year":"1999","journal-title":"The parametrized complexity of some fundamental problems in coding theory. SIAM J. Computing"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB13","doi-asserted-by":"crossref","unstructured":"E. Dalhaus, D.S. Johnson, C.H. Papadimitriou, P. Seymour and M. Yannakakis. The complexity of multiway cuts. Proc. 24th Annual ACM Symp. on the Theory of Computing (STOC) (1992), 241\u2013251.","DOI":"10.1145\/129712.129736"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB14","doi-asserted-by":"crossref","unstructured":"M. Fellows. Parameterized complexity: the main ideas, connetions to heuritics and research frontiers. Proc. ISAAC 2001, Springer-Verlag, Lecture Notes in Computer Science, 2223 (2001), 291\u2013307.","DOI":"10.1007\/3-540-45678-3_26"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB15","doi-asserted-by":"crossref","unstructured":"U. Feige, R. Krauthgamer and K. Nissin. Approximating the minimu bisection size. Proc. 32nd Annual ACM Symposium on the Theory of Computing (STOC) (2000), 530\u2013536.","DOI":"10.1145\/335305.335370"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB16","unstructured":"U. Feige, R. Krauthgamer and K. Nissim. On cutting a few vertices from a graph. Manuscript, 2001."},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB17","doi-asserted-by":"crossref","unstructured":"C. Friedrich, and, M.E. Graph Drawing in Motion II In Proceedings of the 9th International Symposium on Graph Drawing, Springer Verlag Lecture Notes in Computer Science 2265. Page: 220\u2013231. Ed: Mutzel, P.; Junger, M.; Leipert, S.","DOI":"10.1007\/3-540-45848-4_18"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB18","doi-asserted-by":"crossref","unstructured":"N. Garg, V. V. Vazirani, and M. Yannakakis. Multiway Cuts in Directed and Node Weighted Graphs, In Proc. 21 st ICALP, Lecture Notes in Computer Science 820, Springer-Verlag, 1994 487\u2013498.","DOI":"10.1007\/3-540-58201-0_92"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB19","doi-asserted-by":"crossref","unstructured":"O. Goldschmidt and D.S. Hochbaum. Polynomial algorithm for the \u03ba-cut problem. Proc. 29th Annual Symp. on the Foundations of Computer Science (FOCS) (1988), 444\u2013451.","DOI":"10.1109\/SFCS.1988.21960"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB20","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/moor.19.1.24","article-title":"A polynomial algorithm for the \u03ba-cut problem for fixed \u03ba","volume":"19","author":"Goldschmidt","year":"1994","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB21","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB22","doi-asserted-by":"crossref","unstructured":"T.F. Gonalez. On the computational complexity of clustering and related problems. Proc. 10th IFIP Conference on System Modeling and Optimization (1981), 174\u2013182.","DOI":"10.1007\/BFb0006133"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB23","doi-asserted-by":"crossref","unstructured":"M. Grohe. The parameterized complexity of database queries. Proc. 20th ACM Symposium on Principles of Database Systems (PODS) (2001), 82\u201392.","DOI":"10.1145\/375551.375564"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB24","series-title":"Clustering Algorithms","author":"Hartigan","year":"1975"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB25","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/opre.37.6.865","article-title":"Optimization by simulated annealing: an experimental evaluation; Part 1 graph partitioning","volume":"37","author":"Johnson","year":"1989","journal-title":"Operations Research"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB26","author":"King","year":"1994","journal-title":"Private communication"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB27","doi-asserted-by":"crossref","unstructured":"S. Khanna and R. Motwani, \u201cTowards a Syntactic Characterization of PTAS,\u201d in: Proc. STOC 1996, ACM Press (1996), 329\u2013337.","DOI":"10.1145\/237814.237979"},{"issue":"4","key":"10.1016\/S1571-0661(04)81014-4_NEWBIB28","first-page":"601","volume":"43","author":"Karger","year":"1996","journal-title":"A new approach to the minimum cut problem. Journal of the ACM"},{"issue":"8","key":"10.1016\/S1571-0661(04)81014-4_NEWBIB29","first-page":"68","volume":"32","author":"Karypis","year":"1999","journal-title":"Chameleon: Hierarchical clustering using dynamic modeling. Computer"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB30","doi-asserted-by":"crossref","unstructured":"A. J. Quigley and P. Eades. FADE: graph drawing, clustering and visual abstraction. In Proceedings of the Eighth International Symposium on Graph Drawing, Williamsburg Virginia, USA, September 2000. Springer Verlag Lecture Notes in Computer Science 1984. Page: 197\u2013210. Ed: Marks, J.","DOI":"10.1007\/3-540-44541-2_19"},{"issue":"1","key":"10.1016\/S1571-0661(04)81014-4_NEWBIB31","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1137\/S0097539792251730","article-title":"Finding \u03ba cuts with in twice the optimal","volume":"24","author":"Saran","year":"1995","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB32","series-title":"Simulated annealing tabu search algorithms for multiway graph partitioning. Journal of Circuits, Systems and Computers 2","first-page":"159","year":"1992"},{"key":"10.1016\/S1571-0661(04)81014-4_NEWBIB33","doi-asserted-by":"crossref","unstructured":"O. Zamir and O. Etzioni. Web document clustering: a feasibility demonstration. In Proceedings of the 21st International ACM SIGIR Conference on Research and Development in Information Retrieval(SIGIR'98), pages 46\u201354, 1998.","DOI":"10.1145\/290941.290956"}],"container-title":["Electronic Notes in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066104810144?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571066104810144?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T07:13:10Z","timestamp":1585897990000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571066104810144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":33,"alternative-id":["S1571066104810144"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0661(04)81014-4","relation":{},"ISSN":["1571-0661"],"issn-type":[{"value":"1571-0661","type":"print"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}