Efficient approximation of convex recolorings

DOI10.1016/J.JCSS.2007.03.006MaRDI QIDQ2643731zbMATH OpenOpenAlexFDO

Authors Shlomo Moran, Sagi Snir

Publication date 27 August 2007

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2007.03.006

zbMATH Keywords

approximation algorithmsconvex recoloringlocal ratio techniquephylogenetic trees

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• On the complexity of solving or approximating convex recoloring problems
• 1.5-approximation algorithm for the 2-convex recoloring problem
• 1.5-approximation algorithm for the 2-convex recoloring problem
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• The convex recoloring problem: polyhedra, facets and computational experiments
• Hardness and inapproximability of convex recoloring problems
• Improved approximation algorithm for convex recoloring of trees
• Approximation and Online Algorithms

Cites work

• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
• A Polynomial-Time Algorithm for Near-Perfect Phylogeny
• Algorithms and Data Structures
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Convex tree realizations of partitions
• Efficient algorithms for inferring evolutionary trees
• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• Inferring Evolutionary History From DNA Sequences
• Minimal Mutation Trees of Sequences
• Minimizing phylogenetic number to find good evolutionary trees
• Non deterministic polynomial optimization problems and their approximations
• One for the price of two: a unified approach for approximating covering problems
• SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHS
• The complexity of reconstructing trees from qualitative characters and subtrees
• Two strikes against perfect phylogeny

Cited in

(24)

• Combinatorial optimization in system configuration design
• 1.5-approximation algorithm for the 2-convex recoloring problem
• An extended formulation of the convex recoloring problem on a tree
• Sharp upper and lower bounds on a restricted class of convex characters
• Strong intractability results for generalized convex recoloring problems
• A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
• Strong intractability of generalized convex recoloring problems
• Hardness and inapproximability of convex recoloring problems
• Convex recoloring of paths
• The convex recoloring problem: polyhedra, facets and computational experiments
• Strong inequalities and a branch-and-price algorithm for the convex recoloring problem
• Convex recoloring of paths
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• Testing Convexity Properties of Tree Colorings
• Connection Matrices for MSOL-Definable Structural Invariants
• The complexity of minimum convex coloring
• Algorithms and Data Structures
• Testing convexity properties of tree colorings
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Heuristics for the connected assignment problem in arrays
• Quadratic kernelization for convex recoloring of trees
• On the complexity of generalized chromatic polynomials
• Improved approximation algorithm for convex recoloring of trees
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms

This page was built for publication: Efficient approximation of convex recolorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643731)