Please use this identifier to cite or link to this item: https://doi.org/10.1145/2000807.2000810
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
NP-hardness
Partially colored galled networks
Partially colored trees
Issue Date: 2011
Source: 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. https://doi.org/10.1145/2000807.2000810
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
URI: http://scholarbank.nus.edu.sg/handle/10635/39031
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.

SCOPUSTM   
Citations

7
checked on Dec 7, 2017

WEB OF SCIENCETM
Citations

3
checked on Nov 22, 2017

Page view(s)

52
checked on Dec 11, 2017

Google ScholarTM

Check

Altmetric


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