An extended formulation of the convex recoloring problem on a tree

DOI10.1007/s10107-016-1094-3zbMath1379.92034OpenAlexW2557978323MaRDI QIDQ1675254

Bartosz Filipecki, Mathieu Van Vyve, Kangbok Lee, Sunil Chopra, Minseok Ryu, Sang Ho Shim

Publication date: 27 October 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-016-1094-3

zbMATH Keywords

phylogenetic treesconvex recoloring problem

Mathematics Subject Classification ID

Problems related to evolution (92D15) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items

A GRASP for the convex recoloring problem in graphs ⋮ Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem ⋮ Strong intractability results for generalized convex recoloring problems ⋮ Strong inequalities and a branch-and-price algorithm for the convex recoloring problem ⋮ A heuristic for the convex recoloring problem in graphs ⋮ Mixed-integer programming techniques for the connected max-\(k\)-cut problem

Cites Work

• Unnamed Item
• The convex recoloring problem: polyhedra, facets and computational experiments
• The complexity of minimum convex coloring
• Greedoids
• Improved approximation algorithm for convex recoloring of trees
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• The Steiner tree polytope and related polyhedra
• On imposing connectivity constraints in integer programs
• Subgraph polytopes and independence polytopes of count matroids
• Extended formulations for the \(A\)-cut problem
• The partition problem
• Convex recoloring of paths
• Efficient approximation of convex recolorings
• Partial convex recolorings of trees and galled networks
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• Connected Coloring Completion for General Graphs: Algorithms and Complexity
• On the Complexity of Solving or Approximating Convex Recoloring Problems
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• Algorithms and Data Structures
• Extended formulations in combinatorial optimization