User menu

An extended formulation of the convex recoloring problem on a tree

Bibliographic reference Chopra, Sunil ; Filipecki, Bartosz ; Lee, Kangbok ; Ryu, Minseok ; Shim, Sangho ; et. al. An extended formulation of the convex recoloring problem on a tree. In: Mathematical Programming, Vol. 165, p. 529-548 (2017)
Permanent URL
  1. Bar-Yehuda Reuven, Feldman Ido, Rawitz Dror, Improved Approximation Algorithm for Convex Recoloring of Trees, 10.1007/s00224-007-9069-7
  2. Campêlo Manoel B., Huiban Cristiana G., Sampaio Rudini M., Wakabayashi Yoshiko, On the Complexity of Solving or Approximating Convex Recoloring Problems, Lecture Notes in Computer Science (2013) ISBN:9783642387678 p.614-625, 10.1007/978-3-642-38768-5_54
  3. Campêlo Manoel, Lima Karla R., Moura Phablo F.S., Wakabayashi Yoshiko, Polyhedral studies on the convex recoloring problem, 10.1016/j.endm.2013.10.036
  4. Campêlo Manoel, Freire Alexandre S., Lima Karla R., Moura Phablo F. S., Wakabayashi Yoshiko, The convex recoloring problem: polyhedra, facets and computational experiments, 10.1007/s10107-015-0880-7
  5. Chopra, S., Owen, J.L.: Extended formulations for the A-cut problem. Math. Progr. 73, 7–30 (1996)
  6. Chopra Sunil, Rao M. R., The partition problem, 10.1007/bf01581239
  7. Chor, B., Fellows, M., Ragan, M., Razgon, I., Rosamond, F., Snir, S.: Connected coloring completion for general graphs: algorithms and complexity. Lect. Comput. Sci. 4598, 75–85 (2007)
  8. Conforti Michele, Kaibel Volker, Walter Matthias, Weltge Stefan, Subgraph polytopes and independence polytopes of count matroids, 10.1016/j.orl.2015.06.011
  9. Conforti Michele, Cornuéjols Gérard, Zambelli Giacomo, Extended formulations in combinatorial optimization, 10.1007/s10288-010-0122-z
  10. Goemans Michel X., The Steiner tree polytope and related polyhedra, 10.1007/bf01582064
  11. Kaibel, V.: Extended Formulations in Combinatorial Optimization, arXiv:1104.1023v1 [math.CO] 6 Apr (2011), manuscript
  12. Kammer Frank, Tholey Torsten, The complexity of minimum convex coloring, 10.1016/j.dam.2011.09.022
  13. Kanj Iyad A., Kratsch Dieter, Convex Recoloring Revisited: Complexity and Exact Algorithms, Lecture Notes in Computer Science (2009) ISBN:9783642028816 p.388-397, 10.1007/978-3-642-02882-3_39
  14. Korte, B., Lovász, L., Schrader, R.: Greedoids, Algorithms and Combinatorics, vol. 4. Springer, Berlin (1991)
  15. Lima Karla Roberta, Wakabayashi Yoshiko, Convex recoloring of paths, 10.1016/j.dam.2013.02.034
  16. Moran Shlomo, Snir Sagi, Convex Recolorings of Strings and Trees: Definitions, Hardness Results and Algorithms, Lecture Notes in Computer Science (2005) ISBN:9783540281016 p.218-232, 10.1007/11534273_20
  17. Moran Shlomo, Snir Sagi, Efficient approximation of convex recolorings, 10.1016/j.jcss.2007.03.006
  18. Moran Shlomo, Snir Sagi, Convex recolorings of strings and trees: Definitions, hardness results and algorithms, 10.1016/j.jcss.2007.10.003
  19. Moran Shlomo, Snir Sagi, Sung Wing-Kin, Partial convex recolorings of trees and galled networks : Tight upper and lower bounds, 10.1145/2000807.2000810
  20. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1988)
  21. Ponta Oriana, Hüffner Falk, Niedermeier Rolf, Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems, Lecture Notes in Computer Science ISBN:9783540792277 p.490-501, 10.1007/978-3-540-79228-4_43
  22. Vanderbeck François, Wolsey Laurence A., Reformulation and Decomposition of Integer Programs, 50 Years of Integer Programming 1958-2008 (2010) ISBN:9783540682745 p.431-502, 10.1007/978-3-540-68279-0_13
  23. Wang, Y., Buchanan, A., Butenko, S.: On Imposing Connectivity Constraints in Integer Programs.