Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Despite the fact that many vertex coloring problems are polynomially solvable on certain graph classes, most of these problems are not "under control" from a polyhedral point of view. The equivalence between optimization and separation suggests the existence of integer programming formulations for these problems whose associated polytopes admit elegant characterizations. In this work we address this issue. As a starting point, we focus our attention on the well-known standard formulation for the classical vertex coloring problem. We present some general results about this formulation and we show that the vertex coloring polytope associated to this formulation for a graph G and a set of colors C corresponds to a face of the stable set polytope of a particular graph SG C. We further study the perfectness of SG C showing that when |C|>2, this graph is perfect if and only if G is a block graph, from which we deduce a complete characterization of the associated coloring polytopes for block graphs. We also derive a new family of valid inequalities generalizing several known families from the literature and we conjecture that this family is sufficient to completely describe the vertex coloring polytope associated to cacti graphs. © 2016 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Polyhedral studies of vertex coloring problems: The standard formulation
Autor:Delle Donne, D.; Marenco, J.
Filiación:Sciences Institute, National University of General Sarmiento, Buenos Aires, Argentina
Computer Sc. Department, FCEN, University of Buenos Aires, Buenos Aires, Argentina
LIMOS, Blaise Pascal University, Clermont-Ferrand, France
Palabras clave:Polyhedral characterization; Standard formulation; Vertex coloring; Characterization; Coloring; Integer programming; Problem solving; Topology; Block graphs; Integer programming formulations; Polyhedral studies; Polynomially solvable; Stable set polytope; Valid inequality; Vertex coloring; Vertex coloring problems; Graph theory
Año:2016
Volumen:21
Página de inicio:1
Página de fin:13
DOI: http://dx.doi.org/10.1016/j.disopt.2016.05.001
Título revista:Discrete Optimization
Título revista abreviado:Discrete Optim.
ISSN:15725286
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_15725286_v21_n_p1_DelleDonne

Referencias:

  • Biro, M., Hujter, M., Tuza, Z., Precoloring extension. I. Interval graphs (1992) Discrete Math., 100 (1-3), pp. 267-279
  • Bonomo, F., Cecowski, M., Between coloring and list-coloring: μ-coloring (2005) Electron. Notes Discrete Math., 19, pp. 117-123
  • Bonomo, F., Durán, G., Marenco, J., Exploring the complexity boundary between coloring and list-coloring (2009) Ann. Oper. Res., 169 (1), pp. 3-16
  • Tuza, Z., Graph colorings with local constraints - A survey (1997) Discuss. Math.-Graph Theory, 17, pp. 161-228
  • Garey, M., Johnson, D., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , W. H. Freeman
  • Golumbic, M., (2004) Algorithmic Graph Theory and Perfect Graphs, , North Holland
  • Bonomo, F., Faenza, Y., Oriolo, G., On coloring problems with local constraints (2012) Discrete Math., 312 (12-13), pp. 2027-2039
  • Nemhauser, G., Wolsey, L., (1988) Integer and Combinatorial Optimization, , John Wiley & Sons
  • Coll, P., Marenco, J., Méndez-Díaz, I., Zabala, P., Facets of the graph coloring polytope (2002) Ann. Oper. Res., 116 (12), pp. 79-90
  • Méndez-Díaz, I., Zabala, P., A branch-and-cut algorithm for graph coloring (2006) Discrete Appl. Math., 154 (5), pp. 826-847
  • Méndez-Díaz, I., Zabala, P., A cutting plane algorithm for graph coloring (2008) Discrete Appl. Math., 156 (2), pp. 159-179
  • Borndörfer, R., Eisenblätter, A., Grötschel, M., Martin, A., (1998) The Orientation Model for Frequency Assignment Problems, TR 98-01, , ZIB Berlin
  • Delle Donne, D., (2009) Un Algoritmo Branch & Cut para un Problema de Asignación de Frecuencias en Redes de Telefonía Celular, , (Undergraduate thesis) University of Buenos Aires
  • Campêlo, M., Corrêa, R., Frota, Y., Cliques, holes and the vertex coloring polytope (2004) Inform. Process. Lett., 89 (4), pp. 159-164
  • Mehrotra, A., Trick, M., A column generation approach for graph coloring (1996) INFORMS J. Comput., 8 (4), pp. 344-354
  • Burke, E., Marecek, J., Parkes, A., Rudová, H., A supernodal formulation of vertex colouring with applications in course timetabling (2010) Ann. Oper. Res., 179 (1), pp. 105-130
  • Schrijver, A., (2003) Combinatorial Optimization - Polyhedra and Efficiency, , Springer-Verlag
  • Gröschel, M., Lovász, L., Schrijver, A., (1988) Geometric Algorithms and Combinatorial Optimization, , Springer-Verlag
  • Edmonds, J., Maximum matching and a polyhedron with 0,1-vertices (1965) J. Res. Natl. Bur. Stand., 69, pp. 125-130
  • Fekete, P., Marenco, J., (2015) A Complete Description of the Minimum-adjacency Vertex Coloring Polytope for Trees, , Unpublished manuscript
  • Delle Donne, D., Marenco, J., A branch & cut algorithm for the minimum-adjacency vertex coloring problem (2011) Discrete Optim., 8 (4), pp. 540-554
  • Chvátal, V., On certain polytopes associated with graphs (1975) J. Combin. Theory Ser. (B), 18, pp. 138-154
  • Cornaz, D., Jost, V., A one-to-one correspondence between colorings and stable sets (2008) Oper. Res. Lett., 36, pp. 673-676
  • Chudnovsky, M., Robertson, N., Seymour, P.D., Thomas, R., The strong perfect graph theorem (2006) Ann. of Math., 164, pp. 51-229
  • Jansen, K., The optimum cost chromatic partition problem (1997) Lecture Notes in Comput. Sci., 1203, pp. 25-36
  • Bandelt, H., Mulder, H., Distance-hereditary graphs (1986) J. Combin. Theory Ser. B, 41 (2), pp. 182-208

Citas:

---------- APA ----------
Delle Donne, D. & Marenco, J. (2016) . Polyhedral studies of vertex coloring problems: The standard formulation. Discrete Optimization, 21, 1-13.
http://dx.doi.org/10.1016/j.disopt.2016.05.001
---------- CHICAGO ----------
Delle Donne, D., Marenco, J. "Polyhedral studies of vertex coloring problems: The standard formulation" . Discrete Optimization 21 (2016) : 1-13.
http://dx.doi.org/10.1016/j.disopt.2016.05.001
---------- MLA ----------
Delle Donne, D., Marenco, J. "Polyhedral studies of vertex coloring problems: The standard formulation" . Discrete Optimization, vol. 21, 2016, pp. 1-13.
http://dx.doi.org/10.1016/j.disopt.2016.05.001
---------- VANCOUVER ----------
Delle Donne, D., Marenco, J. Polyhedral studies of vertex coloring problems: The standard formulation. Discrete Optim. 2016;21:1-13.
http://dx.doi.org/10.1016/j.disopt.2016.05.001