Please use this identifier to cite or link to this item:
Title: Partial convex recolorings of trees and galled networks: Tight upper and lower bounds
Authors: Moran, S.
Snir, S.
Sung, W.-K. 
Keywords: Convex recoloring
Partially colored galled networks
Partially colored trees
Issue Date: 2011
Citation: Moran, S., Snir, S., Sung, W.-K. (2011). Partial convex recolorings of trees and galled networks: Tight upper and lower bounds. ACM Transactions on Algorithms 7 (4). ScholarBank@NUS Repository.
Abstract: 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. 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 convex recoloring (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. 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. © 2011 ACM.
Source Title: ACM Transactions on Algorithms
ISSN: 15496325
DOI: 10.1145/2000807.2000810
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Aug 6, 2020


checked on Jul 30, 2020

Page view(s)

checked on Aug 4, 2020

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.