{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,18]],"date-time":"2026-11-18T17:01:17Z","timestamp":1795021277898,"version":"4.10.1"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We introduce a graph-theoretic vertex dissolution model that applies to a number of redistribution scenarios, such as gerrymandering in political districting or work balancing in an online situation. The central aspect of our model is the deletion of certain vertices and the redistribution of their load to neighboring vertices in a completely balanced way. We investigate how the underlying graph structure, the knowledge of which vertices should be deleted, and the relation between old and new vertex loads influence the computational complexity of the underlying graph problems. Our results establish a clear borderline between tractable and intractable cases.<\/jats:p>","DOI":"10.1137\/140978880","type":"journal-article","created":{"date-parts":[[2015,5,21]],"date-time":"2015-05-21T11:19:29Z","timestamp":1432207169000},"page":"888-914","source":"Crossref","is-referenced-by-count":10,"title":["Network-Based Vertex Dissolution"],"prefix":"10.1137","volume":"29","author":[{"given":"Ren\u00e9","family":"van Bevern","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert","family":"Bredereck","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiehua","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vincent","family":"Froese","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,5,21]]},"reference":[{"key":"atypb1","unstructured":"R. K. Ahuja, T. L. Magnanti, and J. B. Orlin,\n                      Network Flows: Theory, Algorithms, and Applications\n                      , Prentice-Hall, Englewood Cliffs, NJ, 1993."},{"key":"atypb2","unstructured":"M. Altman,\n                      Districting Principles and Democratic Representation\n                      , Ph.D. thesis, California Institute of Technology, Pasadena, CA, 1998."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(92)90085-Y"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90001-U"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_15"},{"key":"atypb7","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,\n                      Introduction to Algorithms\n                      , 3rd ed., The MIT Press, Cambridge, MA, 2009."},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"B. Courcelle and J. Engelfriet,\n                      Graph Structure and Monadic Second-Order Logic-A Language-Theoretic Approach\n                      , Encyclopedia Math. Appl. 138, Cambridge University Press, Cambridge, UK, 2012.","DOI":"10.1017\/CBO9780511977619"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Springer, London, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb10","unstructured":"J. C. Duque,\n                      Design of Homogeneous Territorial Units: A Methodological Proposal and Applications\n                      , Ph.D. thesis, University of Barcelona, Barcelona, Spain, 2004."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1177\/0160017607301605"},{"key":"atypb12","first-page":"89","author":"Edmonds J.","year":"1970","journal-title":"New York"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"P. Faliszewski and J. Rothe,\n                      Control and bribery in voting\n                      , in Handbook of Computational Social Choice, Cambridge University Press, Cambridge, UK, 2015.","DOI":"10.1017\/CBO9781107446984.008"},{"key":"atypb14","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Springer, Berlin, 2006."},{"key":"atypb15","unstructured":"H. N. Gabow,\n                      Data structures for weighted matching and nearest common ancestors with linking\n                      , in Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '90), 1990, pp. 434-443."},{"key":"atypb16","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"atypb17","first-page":"162","author":"Guo J.","year":"2004","journal-title":"Berlin"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/0401046"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-008-0336-6"},{"key":"atypb20","first-page":"647","author":"Ma\u0142afiejski M.","year":"2005","journal-title":"Berlin"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1080\/03610929508831512"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.44.8.1100"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.12.004"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,\n                      Invitation to Fixed-Parameter Algorithms\n                      , Oxford University Press, Oxford, UK, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"atypb25","unstructured":"R. Niedermeier,\n                      Reflections on multivariate algorithmics and problem parameterization\n                      , in Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS'10), LIPIcs. Leibniz Int. Proc. Inform. 5, Schloss Dagstuhl-Leibniz-Zentrum fu\u0308r Informatik, Wadern, Germany, 2010, pp. 17-32."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.mcm.2008.05.024"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.econlet.2009.06.008"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"V. Vassilevska Williams,\n                      Multiplying matrices faster than Coppersmith-Winograd\n                      , in Proceedings of the 44th ACM Symposium on Theory of Computing (STOC' 12), 2012, pp. 887-898.","DOI":"10.1145\/2213977.2214056"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.07.002"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140978880","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:25:02Z","timestamp":1787322302000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140978880"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140978880"],"URL":"https:\/\/doi.org\/10.1137\/140978880","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}