Navegar

Colección

Datos Estadísticas

Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

A subset S of vertices of a graph G=(V,E) is P 3 -convex if every simple path of three vertices starting and ending in S is contained in S. The P 3 -convex hull of S is the smallest P 3 -convex set containing S and the P 3 -hull number of G is the minimum number of vertices of a subset S such that its convex hull is V. It is a known fact that the calculation of the P 3 -hull number of a graph is NP-hard. In the present work we start the study of this problem from a polyhedral point of view, that is, we pose it as a binary IP problem and we study the associated polytope by exploring several families of facet-defining inequalities. © 2018 Elsevier B.V.

Registro:

Documento: Artículo
Título:Computing the P 3 -hull number of a graph, a polyhedral approach
Autor:Blaum, M.; Marenco, J.
Filiación:Instituto de Ciencias, Universidad Nacional de General Sarmiento, Buenos Aires, Argentina
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave:Combinatorial optimization; Discrete convexity; Facet-defining inequalities; Hull number; Combinatorial optimization; Computational geometry; Set theory; Convex hull; Convex set; Discrete convexity; Facet-defining inequalities; Hull number; NP-hard; Polyhedral approach; Polytopes; Graph theory
Año:2019
Volumen:255
Página de inicio:155
Página de fin:166
DOI: http://dx.doi.org/10.1016/j.dam.2018.08.013
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v255_n_p155_Blaum

Referencias:

  • Araujo, R., Sampaio, R., Szwarcfiter, J., The convexity of induced paths of order three (2013) Electron. Notes Discrete Math., 44, pp. 109-114
  • Centeno, C., Dourado, M., Penso, L., Rautenbach, D., Szwarcfiter, J., Irreversible conversion of graphs (2011) Theoret. Comput. Sci., 412, pp. 3693-3700
  • Centeno, C., Dourado, M., Szwarcfiter, J., On the convexity of paths of length two in undirected graphs (2009) Electron. Notes Discrete Math., 32, pp. 11-18
  • Changat, M., Mathew, J., On triangle path convexity in graphs (1999) Discrete Math., 206, pp. 91-95
  • Chen, N., On the approximability of influence in social networks (2009) SIAM J. Discrete Math., 23 (3), pp. 1400-1415
  • Dourado, M., Protti, F., Szwarcfiter, J., Complexity results related to monophonic convexity (2010) Discrete Appl. Math., 158 (12), pp. 1268-1274
  • Dourado, M., Sampaio, R., Complexity aspects of the triangle path convexity (2016) Discrete Appl. Math., 206, pp. 39-47
  • Dreyer, P., Roberts, F., Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion (2009) Discrete Appl. Math., 157, pp. 1615-1627
  • Kyncl, J., Lidiky, B., Vyskocil, T., Irreversible 2-Conversion Set is NP-Complete, Tech. Rep. (2009), Charles Univ; Marcilon, T., Nascimento, S., Sampaio, R., The maximum time of 2-neighbour bootstrap percolation: Complexity results (2014), pp. 372-383. , Graph-Theoretic Concepts in Computer Science: 40th International Workshop, Nouan-le-Fuzelier, France, June 25–27, 2014. Revised Selected Papers; Riedl, E., Largest and smallest minimal percolating sets in trees (2012) Eelectron. J. Combinatorics, 19 (1), p. 64
  • van de Vel, M.L.J., Theory of Convex Structures (1993), North-Holland; Wolsey, L., Integer Programming (1998), John Wiley and Sons

Citas:

---------- APA ----------
Blaum, M. & Marenco, J. (2019) . Computing the P 3 -hull number of a graph, a polyhedral approach. Discrete Applied Mathematics, 255, 155-166.
http://dx.doi.org/10.1016/j.dam.2018.08.013
---------- CHICAGO ----------
Blaum, M., Marenco, J. "Computing the P 3 -hull number of a graph, a polyhedral approach" . Discrete Applied Mathematics 255 (2019) : 155-166.
http://dx.doi.org/10.1016/j.dam.2018.08.013
---------- MLA ----------
Blaum, M., Marenco, J. "Computing the P 3 -hull number of a graph, a polyhedral approach" . Discrete Applied Mathematics, vol. 255, 2019, pp. 155-166.
http://dx.doi.org/10.1016/j.dam.2018.08.013
---------- VANCOUVER ----------
Blaum, M., Marenco, J. Computing the P 3 -hull number of a graph, a polyhedral approach. Discrete Appl Math. 2019;255:155-166.
http://dx.doi.org/10.1016/j.dam.2018.08.013