Computing the P 3 -hull number of a graph, a polyhedral approach
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 i...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier B.V.
2019
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 04858caa a22006377a 4500 | ||
|---|---|---|---|
| 001 | PAPER-25666 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518205746.0 | ||
| 008 | 190410s2019 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-85054564456 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 030 | |a DAMAD | ||
| 100 | 1 | |a Blaum, M. | |
| 245 | 1 | 0 | |a Computing the P 3 -hull number of a graph, a polyhedral approach |
| 260 | |b Elsevier B.V. |c 2019 | ||
| 270 | 1 | 0 | |m Blaum, M.; Instituto de Ciencias, Universidad Nacional de General SarmientoArgentina; email: mblaum@ungs.edu.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Araujo, R., Sampaio, R., Szwarcfiter, J., The convexity of induced paths of order three (2013) Electron. Notes Discrete Math., 44, pp. 109-114 | ||
| 504 | |a Centeno, C., Dourado, M., Penso, L., Rautenbach, D., Szwarcfiter, J., Irreversible conversion of graphs (2011) Theoret. Comput. Sci., 412, pp. 3693-3700 | ||
| 504 | |a 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 | ||
| 504 | |a Changat, M., Mathew, J., On triangle path convexity in graphs (1999) Discrete Math., 206, pp. 91-95 | ||
| 504 | |a Chen, N., On the approximability of influence in social networks (2009) SIAM J. Discrete Math., 23 (3), pp. 1400-1415 | ||
| 504 | |a Dourado, M., Protti, F., Szwarcfiter, J., Complexity results related to monophonic convexity (2010) Discrete Appl. Math., 158 (12), pp. 1268-1274 | ||
| 504 | |a Dourado, M., Sampaio, R., Complexity aspects of the triangle path convexity (2016) Discrete Appl. Math., 206, pp. 39-47 | ||
| 504 | |a 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 | ||
| 504 | |a 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 | ||
| 504 | |a van de Vel, M.L.J., Theory of Convex Structures (1993), North-Holland; Wolsey, L., Integer Programming (1998), John Wiley and Sons | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Instituto de Ciencias, Universidad Nacional de General Sarmiento, Buenos Aires, Argentina | ||
| 593 | |a Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina | ||
| 690 | 1 | 0 | |a COMBINATORIAL OPTIMIZATION |
| 690 | 1 | 0 | |a DISCRETE CONVEXITY |
| 690 | 1 | 0 | |a FACET-DEFINING INEQUALITIES |
| 690 | 1 | 0 | |a HULL NUMBER |
| 690 | 1 | 0 | |a COMBINATORIAL OPTIMIZATION |
| 690 | 1 | 0 | |a COMPUTATIONAL GEOMETRY |
| 690 | 1 | 0 | |a SET THEORY |
| 690 | 1 | 0 | |a CONVEX HULL |
| 690 | 1 | 0 | |a CONVEX SET |
| 690 | 1 | 0 | |a DISCRETE CONVEXITY |
| 690 | 1 | 0 | |a FACET-DEFINING INEQUALITIES |
| 690 | 1 | 0 | |a HULL NUMBER |
| 690 | 1 | 0 | |a NP-HARD |
| 690 | 1 | 0 | |a POLYHEDRAL APPROACH |
| 690 | 1 | 0 | |a POLYTOPES |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 700 | 1 | |a Marenco, J. | |
| 773 | 0 | |d Elsevier B.V., 2019 |g v. 255 |h pp. 155-166 |p Discrete Appl Math |x 0166218X |w (AR-BaUEN)CENRE-310 |t Discrete Applied Mathematics | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-85054564456&doi=10.1016%2fj.dam.2018.08.013&partnerID=40&md5=5c257c41c76771f9da9b4e027b56949e |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.dam.2018.08.013 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_0166218X_v255_n_p155_Blaum |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v255_n_p155_Blaum |y Registro en la Biblioteca Digital |
| 961 | |a paper_0166218X_v255_n_p155_Blaum |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 86619 | ||