{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T21:01:31Z","timestamp":1770325291130,"version":"3.49.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2011,9,1]],"date-time":"2011-09-01T00:00:00Z","timestamp":1314835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>A coloring of a graph is convex if the vertices that pertain to any color induce a connected subgraph; a partial coloring (which assigns colors to a subset of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring has applications in fields such as phylogenetics, communication or transportation networks, etc.<\/jats:p><jats:p>When a coloring of a graph is not convex, a natural question is how far it is from a convex one. This problem is denoted as<jats:italic>convex recoloring<\/jats:italic>(CR). While the initial works on CR defined and studied the problem on trees, recent efforts aim at either generalizing the underlying graphs or specializing the input colorings.<\/jats:p><jats:p>In this work, we extend the underlying graph and the input coloring to partially colored galled networks. We show that although determining whether a coloring is convex on an arbitrary network is hard, it can be found efficiently on galled networks. We present a fixed parameter tractable algorithm that finds the recoloring distance of such a network whose running time is quadratic in the network size and exponential in that distance. This complexity is achieved by amortized analysis that uses a novel technique for contracting colored graphs that seems to be of independent interest.<\/jats:p>","DOI":"10.1145\/2000807.2000810","type":"journal-article","created":{"date-parts":[[2011,9,27]],"date-time":"2011-09-27T14:02:19Z","timestamp":1317132139000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Partial convex recolorings of trees and galled networks"],"prefix":"10.1145","volume":"7","author":[{"given":"Shlomo","family":"Moran","sequence":"first","affiliation":[{"name":"Technion, Israel"}]},{"given":"Sagi","family":"Snir","sequence":"additional","affiliation":[{"name":"University of California, Berkeley"}]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2011,9,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11671411_5"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of ACiD. 23--35","author":"Bodlaender H. L.","unstructured":"Bodlaender , H. L. , Fellows , M. R. , Langston , M. A. , Ragan , M. A. , Rosamond , F. A. , and Weyer , M . 2006. Kernelization for convex recoloring . In Proceedings of ACiD. 23--35 . Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. 2006. Kernelization for convex recoloring. In Proceedings of ACiD. 23--35."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 13th International Computing and Combinatories Conference (COCOON). Lecture Notes in Computer Science","volume":"4598","author":"Bodlaender H. L.","unstructured":"Bodlaender , H. L. , Fellows , M. R. , Langston , M. A. , Ragan , M. A. , Rosamond , F. A. , and Weyer , M . 2007. Quadratic kernelization for convex recoloring of trees . In Proceedings of the 13th International Computing and Combinatories Conference (COCOON). Lecture Notes in Computer Science , vol. 4598 . Springer, 86--96. Bodlaender, H. L., Fellows, M. R., Langston, M. A., Ragan, M. A., Rosamond, F. A., and Weyer, M. 2007. Quadratic kernelization for convex recoloring of trees. In Proceedings of the 13th International Computing and Combinatories Conference (COCOON). Lecture Notes in Computer Science, vol. 4598. Springer, 86--96."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-006-7135-8"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 13th International Computing and Combinatories Conference (COCOON). Lecture Notes in Computer Science","volume":"4598","author":"Chor B.","unstructured":"Chor , B. , Fellows , M. R. , Ragan , M. A. , Razgon , I. , Rosamond , F. A. , and Snir , S . 2007. Connected coloring completion for general graphs: Algorithms and complexity . In Proceedings of the 13th International Computing and Combinatories Conference (COCOON). Lecture Notes in Computer Science , vol. 4598 . Springer, 75--85. Chor, B., Fellows, M. R., Ragan, M. A., Razgon, I., Rosamond, F. A., and Snir, S. 2007. Connected coloring completion for general graphs: Algorithms and complexity. In Proceedings of the 13th International Computing and Combinatories Conference (COCOON). Lecture Notes in Computer Science, vol. 4598. Springer, 75--85."},{"key":"e_1_2_1_6_1","unstructured":"Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms. MIT Press. Cormen T. Leiserson C. Rivest R. and Stein C. 2001. Introduction to Algorithms. MIT Press."},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer. Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Springer.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_8_1","unstructured":"Garey M. and Johnson D. 1979. Computers and Intractability\u2014A Guide to the Theory of NP-Completeness. Freeman New York. Garey M. and Johnson D. 1979. Computers and Intractability\u2014A Guide to the Theory of NP-Completeness. Freeman New York."},{"key":"e_1_2_1_9_1","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","unstructured":"Golumbic , M. C. 1980. Algorithmic Graph Theory and Perfect Graphs . Academic Press . Golumbic, M. C. 1980. Algorithmic Graph Theory and Perfect Graphs. Academic Press."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Kuhn H. 1955. The Hungarian method for the assignment problem. Naval Res. Log. Quart. 83--97. Kuhn H. 1955. The Hungarian method for the assignment problem. Naval Res. Log. Quart. 83--97.","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.03.006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.10.003"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.05.007"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0128004"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Semple C. and Steel M. 2003. Phylogenetics. Oxford University Press. Semple C. and Steel M. 2003. Phylogenetics. Oxford University Press.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"key":"e_1_2_1_17_1","unstructured":"Weisstein E. W. Bell number. From MathWorld--A Wolfram Web Resource. http:\/\/mathworld.wolfram.com\/BellNumber.html. Weisstein E. W. Bell number. From MathWorld--A Wolfram Web Resource. http:\/\/mathworld.wolfram.com\/BellNumber.html."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000807.2000810","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2000807.2000810","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:00:03Z","timestamp":1750244403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2000807.2000810"}},"subtitle":["Tight upper and lower bounds"],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1145\/2000807.2000810"],"URL":"https:\/\/doi.org\/10.1145\/2000807.2000810","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,9]]},"assertion":[{"value":"2008-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}