Registro:
| Documento: | Tesis de Grado |
| Título: | Problema de dominación eterna para grafos de intervalos |
| Título alternativo: | The eternal dominating problem for interval graphs |
| Autor: | Rinemberg, Martín |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2019 |
| Fecha en portada: | 2019 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Soulignac, Francisco Juan |
| Jurado: | Curcio, Brian Luis; Moyano, Verónica Andrea |
| Idioma: | Español |
| Palabras clave: | PROBLEMA DE DOMINACION ETERNA; GRAFOS DE INTERVALOS; GRAFOS DE INTERVALOS PROPIOS; NUMERO DE CUBRIMIENTO CLIQUE CONEXO; ESTRATEGIA DE DEFENSAETERNAL DOMINATION PROBLEMS; INTERVAL GRAPHS; PROPER INTERVAL GRAPHS; CLIQUECONNECTED COVER NUMBER; DEFENSE STRATEGY |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000588_Rinemberg |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000588_Rinemberg.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000588_Rinemberg |
| Ubicación: | Dep.COM 000588 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Rinemberg, Martín. (2019). Problema de dominación eterna para grafos de intervalos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000588_Rinemberg |
Resumen:
Consideremos un juego por turnos sobre un grafo G = (V, E) jugado por un atacante y un defensor. Inicialmente, el defensor ubica guardias sobre los vértices de G. En cada turno, el atacante elige un vértice v para atacar y el defensor mueve algunos guardias, a vértices adyacentes a sus posiciones actuales, a fin de ubicar al menos un guardia en v. Los problemas de dominación eterna consisten en determinar la mínima cantidad de guardias con las que se puede defender eternamente a G. En particular, γ∞n,1 (G) y γ∞n,n(G) denotan la cantidad mínima de guardias necesarios cuando no y sí se pueden posicionar guardias simultáneamente sobre el mismo vértice, respectivamente. En esta tesis demostramos que si G es un grafo de intervalos, entonces γ∞n,1 (G) = γ∞n,n(G) = θc(G), donde θc(G) es el número de cubrimiento clique-conexo de G. Más aún, damos un algoritmo lineal para computar un conjunto dominante eterno de mínima cardinalidad.
Abstract:
Consider a game that is played by an attacker and a defender on a graph G = (V, E). Initially, the defender places some guards on the vertices of G. In each turn, the attacker chooses a vertex v to attack, while the defender moves some of its guards, to neighbors of their current positions, with the aim of positioning at least one guard on v. The eternal domination problems require to find the minimum number of guards needed to eternally defend G. In particular, γ∞n,1 (G) and γ∞n,n(G) denote the minimum number of guards needed when the defender is forbidden and allowed to move more than one guard to the same vertex, respectively. In this thesis we prove that γ∞n,1 (G) = γ∞n,n(G) = θc(G) for every interval graph G, where θc(G) is the clique-connected cover number of G. Furthermore, we design a linear algorithm to compute an eternal dominating set of minimum cardinality.
Citación:
---------- APA ----------
Rinemberg, Martín. (2019). Problema de dominación eterna para grafos de intervalos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000588_Rinemberg
---------- CHICAGO ----------
Rinemberg, Martín. "Problema de dominación eterna para grafos de intervalos". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2019.https://hdl.handle.net/20.500.12110/seminario_nCOM000588_Rinemberg
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000588_Rinemberg.pdf
Distrubución geográfica
