Un estudio poliedral del cálculo de los números P3-hull y de 2-dominación de un grafo

Mostrar todas las versiones(3)

[fórmulas aproximadas, revisar las mismas en el original]Dado un grafo G=(V, E) y un subconjunto S⊆V se define el conjunto P3-intervalo de S como I(S):=S ∪ {v ∈ V: |S∩N(v)| ≥2}. Cuando el conjunto S verifica que I(S)=S , se dice que es P3-convexo. La clase formada por los conjuntos P3-convexos verif...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Blaum Akerman, Manuela
Otros Autores: Marenco, Javier Leonardo
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2022
Materias:
OPTIMIZACION COMBINATORIA
COMBINATORIA POLIEDRAL
CONVEXIDAD P3
FACETAS
COMBINATORIAL OPTIMIZATION
P3-CONVEXITY
POLYHEDRAL COMBINATORICS
FACETS
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n7049_BlaumAkerman
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id tesis:tesis_n7049_BlaumAkerman
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv spa
topic OPTIMIZACION COMBINATORIA
COMBINATORIA POLIEDRAL
CONVEXIDAD P3
FACETAS
COMBINATORIAL OPTIMIZATION
P3-CONVEXITY
POLYHEDRAL COMBINATORICS
FACETS
spellingShingle OPTIMIZACION COMBINATORIA
COMBINATORIA POLIEDRAL
CONVEXIDAD P3
FACETAS
COMBINATORIAL OPTIMIZATION
P3-CONVEXITY
POLYHEDRAL COMBINATORICS
FACETS
Blaum Akerman, Manuela
Un estudio poliedral del cálculo de los números P3-hull y de 2-dominación de un grafo
topic_facet OPTIMIZACION COMBINATORIA
COMBINATORIA POLIEDRAL
CONVEXIDAD P3
FACETAS
COMBINATORIAL OPTIMIZATION
P3-CONVEXITY
POLYHEDRAL COMBINATORICS
FACETS
description [fórmulas aproximadas, revisar las mismas en el original]Dado un grafo G=(V, E) y un subconjunto S⊆V se define el conjunto P3-intervalo de S como I(S):=S ∪ {v ∈ V: |S∩N(v)| ≥2}. Cuando el conjunto S verifica que I(S)=S , se dice que es P3-convexo. La clase formada por los conjuntos P3-convexos verifica los axiomas que definen una convexidad discreta en V: el conjunto vacío y el conjunto V son P3-convexos, y la intersección de dos conjuntos P3-convexos también lo es. El número de 2-dominación de G es la menor cantidad de elementos de un conjunto S ⊆ V tal que I(S)= V, es decir, tal que todo vértice que no pertenece a S tiene al menos dos vecinos en S . Este parámetro es análogo al bien conocido número de dominación de un grafo. Si se define I^0(S)=S e I^k(S)= I(I^k−1(S )) para k ∈ N, se puede ver que si I^k(S)= I^k+1(S) entonces I^k(S) es la cápsula P3-convexa de S. El número P3-hull de G es la menor cantidad de elementos que tiene un conjunto S cuya cápsula P3-convexa es V, es decir tal que I^k(S)=V para algún k ∈ N0. En la presente tesis nos dedicamos al estudio del número de 2-dominación y del número P3-hull de un grafo desde un punto de vista poliedral, ambos problemas NP-completos en su versión de decisión. A pesar de que las técnicas poliedrales han mostrado su efectividad en la resolución de numerosos problemas de optimización combinatoria, hasta la fecha no se han realizado estudios de este tipo aplicados al cálculo de los parámetros mencionados. Planteamos modelos de programación lineal entera para calcular el número de 2-dominación y el número P3-hull de un grafo, y analizamos distintas propiedades de los poliedros formados por las combinaciones convexas de las soluciones factibles de dichos modelos. Calculamos la dimensión de ambos poliedros, estudiamos la relación que existe entre ellos, presentamos distintas familias de facetas y, por último, brindamos descripciones minimales y completas de los poliedros correspondientes a algunas familias de grafos.[fórmulas aproximadas, revisar las mismas en el original]
author2 Marenco, Javier Leonardo
author_facet Marenco, Javier Leonardo
Blaum Akerman, Manuela
format Tesis doctoral
Tesis doctoral
publishedVersion
author Blaum Akerman, Manuela
author_sort Blaum Akerman, Manuela
title Un estudio poliedral del cálculo de los números P3-hull y de 2-dominación de un grafo
title_short Un estudio poliedral del cálculo de los números P3-hull y de 2-dominación de un grafo
title_full Un estudio poliedral del cálculo de los números P3-hull y de 2-dominación de un grafo
title_fullStr Un estudio poliedral del cálculo de los números P3-hull y de 2-dominación de un grafo
title_full_unstemmed Un estudio poliedral del cálculo de los números P3-hull y de 2-dominación de un grafo
title_sort un estudio poliedral del cálculo de los números p3-hull y de 2-dominación de un grafo
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 2022
url https://hdl.handle.net/20.500.12110/tesis_n7049_BlaumAkerman
work_keys_str_mv AT blaumakermanmanuela unestudiopoliedraldelcalculodelosnumerosp3hullyde2dominaciondeungrafo
AT blaumakermanmanuela apolyhedralstudyofthecomputationofthep3hullandthe2dominationnumbersofagraph
_version_ 1782023084107104256
spelling tesis:tesis_n7049_BlaumAkerman2023-10-02T20:24:38Z Un estudio poliedral del cálculo de los números P3-hull y de 2-dominación de un grafo A polyhedral study of the computation of the P3-hull and the 2-domination numbers of a graph Blaum Akerman, Manuela Marenco, Javier Leonardo OPTIMIZACION COMBINATORIA COMBINATORIA POLIEDRAL CONVEXIDAD P3 FACETAS COMBINATORIAL OPTIMIZATION P3-CONVEXITY POLYHEDRAL COMBINATORICS FACETS [fórmulas aproximadas, revisar las mismas en el original]Dado un grafo G=(V, E) y un subconjunto S⊆V se define el conjunto P3-intervalo de S como I(S):=S ∪ {v ∈ V: |S∩N(v)| ≥2}. Cuando el conjunto S verifica que I(S)=S , se dice que es P3-convexo. La clase formada por los conjuntos P3-convexos verifica los axiomas que definen una convexidad discreta en V: el conjunto vacío y el conjunto V son P3-convexos, y la intersección de dos conjuntos P3-convexos también lo es. El número de 2-dominación de G es la menor cantidad de elementos de un conjunto S ⊆ V tal que I(S)= V, es decir, tal que todo vértice que no pertenece a S tiene al menos dos vecinos en S . Este parámetro es análogo al bien conocido número de dominación de un grafo. Si se define I^0(S)=S e I^k(S)= I(I^k−1(S )) para k ∈ N, se puede ver que si I^k(S)= I^k+1(S) entonces I^k(S) es la cápsula P3-convexa de S. El número P3-hull de G es la menor cantidad de elementos que tiene un conjunto S cuya cápsula P3-convexa es V, es decir tal que I^k(S)=V para algún k ∈ N0. En la presente tesis nos dedicamos al estudio del número de 2-dominación y del número P3-hull de un grafo desde un punto de vista poliedral, ambos problemas NP-completos en su versión de decisión. A pesar de que las técnicas poliedrales han mostrado su efectividad en la resolución de numerosos problemas de optimización combinatoria, hasta la fecha no se han realizado estudios de este tipo aplicados al cálculo de los parámetros mencionados. Planteamos modelos de programación lineal entera para calcular el número de 2-dominación y el número P3-hull de un grafo, y analizamos distintas propiedades de los poliedros formados por las combinaciones convexas de las soluciones factibles de dichos modelos. Calculamos la dimensión de ambos poliedros, estudiamos la relación que existe entre ellos, presentamos distintas familias de facetas y, por último, brindamos descripciones minimales y completas de los poliedros correspondientes a algunas familias de grafos.[fórmulas aproximadas, revisar las mismas en el original] [fórmulas aproximadas, revisar las mismas en el original]Let G=(V, E) be a graph and S⊆V be a subset of vertices. We define the P3-interval set of S as I(S):=S ∪ {v ∈ V:|S∩N(v)| ≥2}. If the subset S verifies that I(S)=S, we say that it is P3-convex. The class of P3-convex sets verifies the axioms defining a discrete convexity in V: the empty set and V are P3-convex, and the intersection of P3-convex sets is also a convex set. The 2-domination number of G is the minimum cardinality of a set S ⊆ V such that I(S) = V, that is to say, such that every vertex not in S has at least two neighbors in S. This parameter is analogous to the well-known domination number of a graph. If we define I^0(S)=S and I^k(S) = I(I^k−1(S)) for k ∈ N, we can see that if I^k(S)= I^k+1(S) then I^k(S) is the P3-convex hull of S. The P3-hull number of G is the minimum cardinality of a set S , such that its P3-convex hull is V, in other words, that I^k(S)=V for some k ∈ N0. In this thesis we study the 2-domination and the P3-hull number of a graph from a polyhedral point of view, both NP-complete problems in their decision version. Although polyhedral techniques have been successfully applied to several combinatorial optimization problems, up to our knowledge there are not studies of this type applied to the computation of the mentioned parameters. We pose integer linear programming models for the calculation of the 2-domination and the P3-hull number of a graph, and we analyze several properties of the polyhedra consisting of convex combinations of feasible solutions. We compute the dimension of both polyhedra, we explore their relationships, we present different families of facets, and, finally, we show complete and minimal descriptions of these polyhedra for some families of graphs.[fórmulas aproximadas, revisar las mismas en el original] Fil: Blaum Akerman, Manuela. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2022-03-07 info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion application/pdf spa info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n7049_BlaumAkerman

Ejemplares similares