Improved approximation algorithm for convex recoloring of trees

DOI10.1007/s00224-007-9069-7zbMath1140.68071OpenAlexW1975960975MaRDI QIDQ927405

Ido Feldman, Dror Rawitz, Reuven Bar Yehuda

Publication date: 6 June 2008

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9069-7

zbMATH Keywords

Approximation algorithmsConvex recoloringLocal ratioPhylogenetic trees

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (9)

A GRASP for the convex recoloring problem in graphs ⋮ 1.5-approximation algorithm for the 2-convex recoloring problem ⋮ Convex Recoloring Revisited: Complexity and Exact Algorithms ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ A heuristic for the convex recoloring problem in graphs ⋮ Quadratic kernelization for convex recoloring of trees ⋮ Hardness and inapproximability of convex recoloring problems ⋮ Exact exponential algorithms to find tropical connected sets of minimum size ⋮ Combinatorial optimization in system configuration design

Cites Work

• Unnamed Item
• Unnamed Item
• One for the price of two: a unified approach for approximating covering problems
• On Generating the N-ary Reflected Gray Codes
• Minimal Mutation Trees of Sequences
• Inferring Evolutionary History From DNA Sequences
• A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Algorithms and Data Structures
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Efficient algorithms for inferring evolutionary trees
• A unified approach to approximating resource allocation and scheduling
• Minimizing phylogenetic number to find good evolutionary trees

This page was built for publication: Improved approximation algorithm for convex recoloring of trees