Efficient approximation of convex recolorings
From MaRDI portal
Publication:2643731
DOI10.1016/j.jcss.2007.03.006zbMath1123.68095OpenAlexW2111929782MaRDI QIDQ2643731
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
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (17)
Sharp upper and lower bounds on a restricted class of convex characters ⋮ 1.5-approximation algorithm for the 2-convex recoloring problem ⋮ An extended formulation of the convex recoloring problem on a tree ⋮ Strong intractability of generalized convex recoloring problems ⋮ Strong intractability results for generalized convex recoloring problems ⋮ Strong inequalities and a branch-and-price algorithm for the convex recoloring problem ⋮ Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems ⋮ Heuristics for the connected assignment problem in arrays ⋮ The complexity of minimum convex coloring ⋮ Quadratic kernelization for convex recoloring of trees ⋮ Hardness and inapproximability of convex recoloring problems ⋮ Convex recoloring of paths ⋮ On the complexity of generalized chromatic polynomials ⋮ Connection Matrices for MSOL-Definable Structural Invariants ⋮ Combinatorial optimization in system configuration design ⋮ Convex Recoloring of Paths ⋮ The convex recoloring problem: polyhedra, facets and computational experiments
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non deterministic polynomial optimization problems and their approximations
- Convex tree realizations of partitions
- The complexity of reconstructing trees from qualitative characters and subtrees
- One for the price of two: a unified approach for approximating covering problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Minimal Mutation Trees of Sequences
- Inferring Evolutionary History From DNA Sequences
- A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies
- A Polynomial-Time Algorithm for Near-Perfect Phylogeny
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHS
- Two strikes against perfect phylogeny
- Algorithms and Data Structures
- Efficient algorithms for inferring evolutionary trees
- Minimizing phylogenetic number to find good evolutionary trees
This page was built for publication: Efficient approximation of convex recolorings