Biblioteca Digital | FCEN-UBA

Biblioteca Digital ¿Por qué?
Objetivos
Impactos
Estadísticas
Documentos
Presentaciones
Notas
Autores y derechos
¿Por qué depositar?
¿Cómo depositar?
Autorización
Depositar y publicar
Editoriales
Publicar mi tesis Formulario Tesis Posgrado
Formulario Tesis Grado
Normativa
Res. CD 2053/05
Res. CD 2533/09
Res. CD 0272/13
Res. CD 2793/15

Colecciones Tesis Doctorales
Fotografías
Publicaciones
Archivo
Libros
Reportes Técnicos

Tesis > TEMA

Computación [ 80 tesis ]

Teoría de Grafos [ 10 tesis ]

Durán, Guillermo Alfredo. "Sobre grafos intersección de arcos y cuerdas en un círculo" (2000) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
Los grafos arco-circulares son los grafos intersección de arcos alrededor de un círculo. Presentamos en esta tesis los principales resultados conocidos sobre esta clase y definimos las principales subclases. Mostramos como a partir de la caracterización formulada por Tucker para grafos arco-circular propios surgen nuevas caracterizaciones para esta subclase y deducimos características de las estructuras prohibidas minimales para arco-circulares. Se estudian todas las posibles intersecciones de las subclases definidas, mostrando un ejemplo minimal en cada una de las regiones que se generan, excepto en una de ellas que se demuestra que es vacía. Este resultado asegura que dado un grafo arco-circular propio no unitario, si es clique-Helly debe ser arco-circular Helly. Los grafos circulares son los grafos intersección de cuerdas dentro de un círculo. También aquí presentamos una reseña de los resultados más importantes y definimos las principales subclases, demostrando algunas relaciones de inclusión entre ellas. Damos una condición necesaria para que un grafo sea circular Helly y conjeturamos que también es suficiente. De ser correcta esta conjetura tendríamos una caracterización y también un reconocimiento polinomial para esta subclase. Se muestra como a partir de la mencionada caracterización de Tucker para grafos arco-circular propios y de un teorema de caracterización de Bouchet para los circulares surgen estructuras prohibidas minimales para esta clase. Analizamos también todas las posibles intersecciones de las subclases definidas, mostrando un ejemplo minimal en cada una de las regiones que se generan. Estudiamos una superclase de los grafos circulares: los grafos overlap de arcos circulares. Se muestran nuevas propiedades sobre esta clase, poniendo énfasis en su relación con los grafos arco-circulares y los circulares. Damos una condición necesaria para que un grafo sea overlap de arcos circulares. Probarnos la polinomialidad de encontrar una partición en cliques mínima para la clase de grafos que no contienen como subgrafo inducido ciclos inducidos impares de longitud mayor ó igual a 5 ni una rueda de 5 vétices ni un abanico de 5 vértices. Usamos para ello resultados de teoría poliedral para programación lineal entera. Extendemos este mismo resultado para cubrimiento mínimo de cliques por vértices. Aplicamos estos resultados a grafos circular HelIy sin agujeros impares, lo que es interesante pues estos problemas son NP-Hard para la clase general de los grafos y de complejidad desconocida para la clase de los grafos circulares. También demostramos que el problema de cubrimiento mínimo de cliques por vértices es polinomial para grafos arco-circular Helly. Por último, presentamos algunas conclusiones que surgen de este trabajo y las líneas futuras de investigación en estos tópicos, destacando algunos problemas interesantes que permanecen abiertos.

Méndez Díaz, Isabel. "Problema de coloreo de Grafos : un estudio poliedral y un algoritmo Branch-and-Cut" (2003) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
El problema de coloreo de grafos, PCG, es uno de los problemas clásicos de la teoría de grafos y es estudiado desde el siglo XIX. Más allá del interés teórico, tiene una significativa importancia práctica debida a las numerosas situaciones de la vida real en las cuales surgen problemas que pueden ser modelados como un problema de coloreo de grafos. PCG pertenece a la clase de problemas NP-Hard, es decir que no se conoce un algoritmo polinomial para resolverlo. Existe en la bibliografía gran cantidad de trabajos proponiendo algoritmos para su resolución especialmente heurísticas y en menor medida algoritmos exactos. Como muchos problemas de Optimización Combinatoria, PCG se puede modelar como un problema de programación lineal entera. Los algoritmos Branch-and- Cut son la herramienta más efectiva que se conoce para resolver un modelo de programación lineal entera. En particular, las implementaciones que usan desigualdades válidas del poliedro asociado al modelo han mostrado ser las más efectivas. Tal vez una de las mayores dificultades de este abordaje se presenta cuando el problema de programación lineal entera tiene la propiedad de simetría, es decir que existen múltiples soluciones con el mismo valor de la función objetivo. En estos casos, los algoritmos habituales disminuyen en gran medida su performance. El objetivo de esta tesis es abordar la resolución del problema de coloreo de grafos mediante modelos de programación entera binaria que parcialmente eliminen soluciones simétricas. Con este fin, proponemos varios modelos que tratan la simetría del problema con diferentes criterios. Estudiamos los poliedros asociados a estos modelos y desarrollamos e implementamos un algoritmo Branch-and-Cut donde utilizamos este estudio poliedral y estrategias particulares que guían la búsqueda evitando explorar sobre soluciones simétricas. Se presentan resultados que demuestran que este algoritmo es capaz de competir exitosamente con los algoritmos exactos conocidos.

Abstract:
The graph coloring problem, PCG, is perhaps one of the oldest and most well-known problems in graph theory. Nowadays, it arises in many applications such as scheduling, timetabling, electronic bandwidth allocation and sequencing. PCG is known to be NP-hard for arbitrary graphs. The practical importance of the problem makes neccesary to devise algorithms capable of solving, in acceptable computational times, medium to moderate instances arising in real-world applications. A lot of work has been spent in an attempt to develop efficient algorithms for the problem, mainly by using heuristic techniques to deal with large instances. Relatively few methods for solving the problem exactly can be found in the literature. Like most optimization problems on graphs, PCG can be formulated as a linear integer programming problem. LP-based Branch-and-Cut algorithms are currently the most successfull tool to deal with these models computationally. However, the amount of research effort spent in attempts to solve PCG by this method is not comparable with that devoted to other problems, like TSP or maximum stable set. If the integer programming formulation exhibits symmetries, i.e. many solutions exist with the same optimal value, it turns out that Branch-and-Cut exhibts poor performance even for small instances. The classical models for PCG suffered from this problem. In this thesis, we present new integer programming formulations that reduce the number of feasible symmetrical solutions. We develop a polyhedral study of the polytope associated with the proposed models in order to derive families of facet-defining inequalities. Branch-and-Cut implementations that take advantage of the particular structure of the problem under consideration have proved to be the most successfull. In this sense, the use of cutting planes arising from a polyhedral study of the feasible solution set allowed many instances of hard combinatorial optimization problems to be solved to proven optimality for the first time. We develop a Branch-and-Cut algorithm based on our theoretical polyhedral results. We also take into account many others factors like preprocessing, search and branching strategies, lower and upper bounds and streghthening of the LP-relaxation. We present computational results showing that our algorithm performance is successful when compared to known exact algorithms.

Bonomo, Flavia. "Sobre subclases y variantes de los grafos perfectos" (2005) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
Los grafos perfectos fueron definidos por Claude Berge en 1960. Un grafo G es perfecto cuando para todo subgrafo inducido H de G, el número cromático de H es igual al tamaño de un subgrafo completo máximo de H. Los grafos perfectos son de gran interés desde el punto de vista algoritmo: si bien los problemas de determinar la clique máxima y el número cromático de un grafo son NP-completos, éstos se resuelven en tiempo polinomial para grafos perfectos. Desde entonces, fueron definidas y estudiadas gran cantidad de variantes de los grafos perfectos. Entre ellas, los grafos clique-perfectos. Una clique en un grafo es un subgrafo completo maximal con respecto a la inclusión. Un transversal de las cliques de un grafo G es un subconjunto de vértice que interseca a todas las cliques de G. Un conjunto de cliques independientes es un conjunto de cliques disjuntas dos a dos. Un grafo G es clique-perfecto si el tamaño de un transversal de las cliques mínimo coincide con el de un conjunto de cliques independientes máximo, para cada subgrafo inducido de G. El término "clique-perfecto" fue introducido por Guruswami y Pandu Rangan en 2000, pero la igualdad de esos parámetro fue estudiada previamente por Berge en el contexto de hipergrafos balanceados. En 2002, Chudnovsky, Robertson, Seymour y Thomas demostraron una caracterización de los grafos perfectos por subgrafos prohibidos minimales, cerrando una conjetura abierta durante 40 años. También durante el año 2002 fueron presentados dos trabajos, uno de ellos de Chudnovsky y Seymour, y el otro de Cornuéjols, Liu y Vuskovic, que mostraban que el reconocimiento de esta clase era polinomial, resolviendo otro problema abierto formulado mucho tiempo atrás. La lista de subgrafos prohibidos minimales para la clase de grafos clique-perfectos no se conoce aún, y También es una pregunta abierta la complejidad del problema de reconocimiento. En esta tesis presentamos resultados parciales en estas direcciones, es decir, caracterizamos los grafos cliqueperfectos por subgrafos prohibidos minimales dentro de ciertas clases de grafos, a saber,

Abstract:
Perfect graphs were defined by Claude Berge in 1960. A graph G is perfect whenever for every induced subgraph H of G, the chromatic number of H equals the cardinality of a maximum complete subgraph of H. Perfect graphs are very interesting from an algorithmic point of view: while determining the clique number and the chromatic number of a graph are NP-complete problems, they are solvable in polynomial time for perfect graphs. Since then, many variations of perfect graphs were defined and studied, including the class of clique-prefect graphs. A clique in a graph is a complete subgraph maximal under inclusion. A clique-transversal of a graph G is a subset of vertices meeting all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. The term clique-perfect" was introduced by Guruswami and Pandu Rangan in 2000, but the equality of these parameters had been previously studied by Berge in the context of balanced hypergraphs. A characterization of perfect graphs by minimal forbidden subgraphs was recently proved by Chudnovsky, Robertson, Seymour and Thomas, and a polynomial time recognition algorithm for this class of graphs has been developed by Chudnovsky, Cornuéjols, Liu, Seymour and Vusković. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning cliqueperfect graphs is the complexity of the recognition problem. In this thesis, we present partial results in these directions, that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph is either a line graph, or claw-free hereditary clique-Helly, or diamond-free, or a Helly circular-arc graph. Almost all of these characterizations lead to polynomial time recognition algorithms for clique-perfection in the corresponding class of graphs. Berge defined a hypergraph to be balanced if its vertex-edge incidence matrix is balanced, that is, if it does not contain the vertex-edge incidence matrix of an odd cycle as a submatrix. In 1998, Dahlhaus, Manuel and Miller consider this concept applied to graphs, defining a graph to be balanced when its vertex-clique incidence matrix is balanced. Balanced graphs are an interesting subclass in the intersection of perfect and clique-perfect graphs. We give two new characterizations of this class, the first one by forbidden subgraphs and the second one by clique subgraphs. Using domination properties we define four subclasses of balanced graphs. Two of them are characterized by 0-1 matrices and can be recognized in polynomial time. Furthermore, we propose polynomial time combinatorial algorithms for the stable set problem, the clique-independent set problem and the clique-transversal problem in one of these subclasses. Finally, we analyze the behavior of balanced graphs and these four subclasses under the clique graph operator.

Tobis, Enrique Augusto. "Métodos algebraicos para problemas discretos" (2009) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Soulignac, Francisco Juan. "Sobre grafos arco-circulares propios y helly" (2010) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
Un modelo arco-circular es un par M=(C,A) donde C es un círculo y A es una familia de arcos de C. Si ningún arco se encuentra contenido en otro arco entonces decimos que M es propio, mientras que si A satisface la propiedad de Helly entonces decimos que M es Helly. Un grafo G es arco-circular si es el grafo de intersección de los arcos de un modelo arco-circular M. Si además M es propio (resp. Helly) entonces decimos que G es un grafo arco-circular propio (resp. Helly). Los grafos arco-circulares y sus subclases son estudiados con especial atención desde fines de la década de 1960, y al día de hoy la literatura al respecto es muy vasta. Esto se debe a la gran cantidad de aplicaciones que poseen en áreas tan diversas como las bases de datos, la genética, la arqueología, la psicología, la economía, etc., y a las propiedades de su estructura combinatoria. El problema de reconocimiento de grafos arco-circulares, y de varias de sus subclases, puede ser resuelto en tiempo lineal. Más aún, un modelo arco-circular puede ser generado en tiempo lineal. En esta tesis estudiamos la clase de grafos arco-circulares desde una perspectiva estructural y algorítmica, concentrándonos principalmente en las subclases de grafos arco-circulares propios y Helly.

Abstract:
A circular-arc model M=(C,A) is a circle C together with a collection A of arcs of C. If no arc is contained in any other, then M is a proper circular-arc model, and if A satisfies the Helly Property, then M is a Helly circular-arc model. A graph G is a circular-arc graph if it is the intersection graph of the arcs of a circular-arc model M. If in addition M is a proper (resp. Helly) circular-arc model then G is a proper (resp. Helly) circular-arc graph. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature since the late 1960's. This is because of their applications in areas as diverse as databases, genetics, archeology, psychology, economics, among others, and because of their nice combinatorial structure. Linear time recognition algorithms have been described both for the general class and for some of its subclasses. Moreover, a circular-arc model can be obtained within the same amount of time. In this thesis we study circular-arc graphs from a structural and algorithmic point of view, with our focus on the proper and Helly subclasses.

Safe, Martín Darío. "Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König" (2011) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
Un grafo es balanceado si su matriz clique no contiene como submatriz ninguna matriz de incidencia arista-vértice de un ciclo impar. Se conoce una caracterización para estos grafos por subgrafos inducidos prohibidos, pero ninguna que sea por subgrafos inducidos prohibidos minimales. En esta tesis probamos caracterizaciones por subgrafos inducidos prohibidos minimales para los grafos balanceados restringidas a ciertas clases de grafos y mostramos que dentro de algunas de ellas conducen a algoritmos lineales para reconocer el balanceo. Un grafo es clique-perfecto si en cada subgrafo inducido el mínimo número de vértices que intersecan todas las cliques coincide con el máximo número de cliques disjuntas dos a dos. Contrariamente a los grafos perfectos, para estos grafos no se conoce una caracterización por subgrafos inducidos prohibidos ni la complejidad del problema de reconocimiento. En esta tesis caracterizamos los grafos clique-perfectos por subgrafos inducidos prohibidos dentro de dos clases de grafos, lo que implica algoritmos de reconocimiento polinomiales para la clique-perfección dentro de dichas clases. Un grafo tiene la propiedad de Kőnig si el mínimo número de vértices que intersecan todas las aristas iguala al máximo número de aristas que no comparten vértices. En esta tesis caracterizamos estos grafos por subgrafos prohibidos, lo que nos permite también caracterizar los grafos arista-perfectos por arista-subgrafos prohibidos.

Abstract:
A graph is balanced if its clique-matrix contains no edge-vertex incidence matrix of an odd cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs was given, no such characterization by minimal forbidden induced subgraphs is known. In this thesis, we prove minimal forbidden induced subgraph characterizations of balanced graphs, restricted to graphs that belong to certain graph classes. We also show that, within some of these classes, our characterizations lead to linear-time recognition algorithms for balancedness. A graph is clique-perfect if, in each induced subgraph, the minimum size of a set of vertices meeting all the cliques equals the maximum number of vertex-disjoint cliques. Unlike perfect graphs, neither a forbidden induced subgraph characterization nor the complexity of the recognition problem are known for clique-perfect graphs. In this thesis, we characterize clique-perfect graphs by means of forbidden induced subgraphs within two different graph classes, which imply polynomial-time recognition algorithms for clique-perfectness within the same two graph classes. A graph has the Kőnig property if the minimum number of vertices needed to meet every edge equals the maximum size of a set of vertex-disjoint edges. In this thesis, we characterize these graphs by forbidden subgraphs, which, in its turn, allows us to characterize edge-perfect graphs by forbidden edge-subgraphs.

Severin, Daniel E.. "Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos" (2012) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
Los problemas de coloreo de grafos constituyen una familia de problemas de una gran relevancia tanto teórica como práctica. Todos ellos son variaciones del problema del coloreo clásico, cuyo estudio se inició en el Siglo XIX. El origen de estas variaciones radica en las restricciones adicionales que imponen las aplicaciones a problemas de la vida real. En esta tesis abordamos en particular el Problema de Coloreo Equitativo en Grafos. Como muchos problemas de Optimización Combinatoria, el Problema de Coloreo Equitativo es un problema NP-difícil. Los algoritmos Branch-and-Cut basados en el estudio poliedral de una formulación del problema como programa lineal entero, son la herramienta más efectiva que se conoce para la resolución exacta de problemas NP-difíciles. En esta tesis se propone un modelo de programación lineal entera para el Problema del Coloreo Equitativo y se estudia el poliedro asociado. Se derivan varias familias de desigualdades validas y se prueba que siempre definen caras de alta dimensión, lo cual es un buen indicador para la utilización de las mismas como planos de corte. Finalmente, se desarrolla e implementa un algoritmo Branch-and-Cut para el Problema de Coloreo Equitativo que resulta altamente competitivo con los algoritmos exactos conocidos.

Abstract:
The graph coloring problems constitute a family of problems of great theoretical and practical relevance. All of them are variations of the classical coloring problem, whose study began in the nineteenth century. The origin of these variations arises from the additional restrictions imposed by applications to real life problems. In particular, this thesis deals with the Equitable Graph Coloring Problem. Like many combinatorial optimization problems, the Equitable Coloring Problem is NP-hard. It is known that Branch-and-Cut algorithms based on the polyhedral study of a formulation of the problem as an integer linear program, are the most effective tool for solving NP-hard problems. This thesis proposes a linear integer programming model for the Equitable Coloring Problem and studies the polytope associated to that model. Several families of valid inequalities that define faces of high dimension are derived in order to use them later as cutting planes. Finally, a Branch-and-Cut algorithm for the Equitable Coloring Problem that is highly competitive against known exact algorithms is developed.

Koch, Ivo Valerio. "Un enfoque algorítmico sobre algunas variantes del problema de coloreo de grafos y el problema de conjunto independiente máximo" (2014-08-21) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
En esta Tesis estudiamos variantes del problema de coloreo de grafos para varias familias de grafos, y analizamos el problema del conjunto independiente máximo bajo un enfoque de generación de planos de corte. En el problema del k; i-coloreo, asignamos conjuntos de colores de cardinalidad k a los vértices de un grafo G, de manera que los conjuntos que correspondan a vértices adyacentes en G intersequen en no más de i elementos y la cantidad total de colores usados sea mínima. Esta cantidad mínima recibe el nombre de número k; i-cromático y es denotada por Xik(G). Este parámetro, que generaliza el número cromático X01(G), es tan difícil de trabajar que su valor es desconocido aún para grafos completos. Desarrollamos un algoritmo de orden lineal para el cómputo de Xik para ciclos y generalizamos este resultado a grafos cactus. Adicionalmente, estudiamos la relación entre este problema en grafos completos y un problema abierto clásico de teoría de códigos. Un b-coloreo de un grafo es un coloreo tal que cada clase color admite un vértice adyacente a por lo menos un vértice perteneciente a cada una de las demás clases color. El número b-cromático de un grafo G, denotado como Xb(G), es el máximo número t tal que G admite un b-coloreo con t colores. Describimos un algoritmo polinomial para computar el número b-cromático de la clase de los grafos P4-tidy y estudiamos para esta clase dos propiedades conocidas: la b-continuidad y la b-monotonía. Estudiamos además la versión sobre aristas del b-coloreo y su índice b-cromático asociado. Presentamos cotas para el índice b-cromático del producto directo de grafos y damos resultados generales para varios productos directos de grafos regulares. Introducimos también un modelo sencillo de programación lineal para el b-coloreo de aristas, que utilizamos para calcular resultados exactos para el producto directo de algunas clases de grafos. Finalmente, proponemos un nuevo método de generación de planos de corte para el problema del conjunto independiente máximo. El algoritmo genera desigualdades de rango y otras desigualdades válidas, y utiliza un procedimiento de lifting basado en la resolución del conjunto independiente máximo con pesos sobre un grafo de menor tamaño.

Abstract:
In this Thesis we study variants of the graph coloring problem for several families of graphs, and we address the stable set problem under a new cutting plane generation approach. In the k; i-coloring problem, we assign sets of colors of size k to the vertices of a graph G, so that the sets which belong to adjacent vertices of G intersect in no more than i elements and the total number of colors used is minimum. This minimum number of colors is called k; i-chromatic number and is denoted by Xik(G). This parameter, which generalizes the chromatic number X01 (G), is so difficult to deal with, that its value is unknown even for complete graphs. We develop a linear time algorithm to compute Xik for cycles and generalize the result to cacti. Further, we study the relation between this problem on complete graphs and a classic open problem in coding theory. A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by Xb(G), is the maximum number t such that G admits a b-coloring with t colors. We describe a polynomial time algorithm to compute the b-chromatic number for the class of P4-tidy graphs and study this class for two known properties: the b-continuity and the b-monotonicity. We study also the edge version of the b-coloring problem and its associated b-chromatic index for the direct product of graphs and provide general results for many direct products of regular graphs. We introduce a simple linear programming model for the b-edge coloring problem, which we use for computing exact results for the direct product of some special graph classes. Finally, we propose a general procedure for generating cuts for the maximum stable set problem. The algorithm generates both rank and non-rank valid inequalities, and employs a lifting method based on the resolution of a maximum weighted stable set problem on a smaller graph.

Mizrahi, Michel Jonathan. "Algoritmos y complejidad para algunos problemas de dominación" (2014-11-21) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
Los problemas de dominación forman un área de investigación en crecimiento, debido a la cantidad de aplicaciones que pueden modelar, entre las cuales podemos nombrar redes sociales, sistemas distribuidos, redes biológicas, problemas de localización de instalaciones, etc. En esta tesis estudiamos los siguientes problemas de dominación (i) el conjunto dominante mínimo, (ii) dominación romana, (iii) dominación eficiente por vértices, (iv) dominación eficiente por aristas (también conocida como matching inducido dominante), (v) dominación perfecta por vértices (vi) dominación perfecta por aristas, y (vii) subgrafo cordal máximo inducido sin vertices propiamente dominados (también conocido como eliminación de vértices para formar clusters). Para el problema (i) determinamos su complejidad para clases de grafos donde se prohiben subgrafos inducidos con a lo sumo cuatro vértices. Estudiamos los problemas (i) y (ii) para varias subclases de grafos P5-free, dando algoritmos eficientes, robustos y simples en ambos casos. Algoritmos de complejidad lineal para grafos arco-circulares fueron presentados para los problemas (iv), (v), (vi) usando algoritmos existentes para el problema (iii). Damos tres algoritmos de tiempo exponencial para resolver el problema (iv) en grafos generales. Además, para el problema (iv), presentamos algoritmos de complejidad O(n) restringidos a grafos cordales, dualmente-cordales, biconvexos, y claw-free. Estudiamos cuatro variantes del problema (vii) y presentamos algoritmos eficientes para todos ellos cuando nos restringimos a grafos de intervalos propios, grafos de intervalos, grafos arco-circulares, grafos de permutación, y grafos trapezoide. Por otro lado, probamos que las cuatro variantes son NP-Dificil para grafos bipartitos. Finalmente, mostramos que dos variantes son NP-Dificil para grafos split, mientras que las otras dos variantes se pueden resolver en tiempo polinomial.

Abstract:
Domination is a growing research area in graph theory, with a vast number of applications across different disciplines, which include social networks, distributed computing, biological networks, facility location problems, etc. In this thesis we studied the following domination problems (i) minimum dominating set problem (ii) Roman domination (iii) efficient vertex domination (iv) efficient edge domination (also known as dominating induced matching or DIM) (v) perfect vertex domination (vi) perfect edge domination (vii) maximum induced chordal subgraph without properly dominated vertices (also known as cluster vertex deletion). For problem (i) we determined its complexity for graph classes defined by forbidding as induced subgraphs all graphs with at most four vertices. We studied problems (i) and (ii) for some subclasses of P5-free graphs, giving efficient, robust and simple algorithms for both of them. Linear time algorithms restricted to circular-arc graphs were presented for problems (iv), (v), (vi) using existent linear algorithms from problem (iii). We described three exact exponential time algorithms solving problem (iv) for general graphs. Also, for problem (iv), O(n) time algorithms were given restricted to chordal, dually-chordal, bi-convex and claw-free graphs. We studied four variants of problem (vii) and presented efficient algorithms for all variants whenever the graphs were proper-interval graphs, interval graphs, circular-arc graphs, permutation graphs and trapezoid graphs. On the other hand we proved that the four variants are NP-Hard for bipartite graphs. Finally we showed that two of the variants are NP-Hard for split graphs while the other two variants are polynomially solvable.

Tabacman, Maximiliano. "Métricas de complejidad de grafos para clasificación en múltiples dominios" (2016-05-02) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
El objetivo de esta tesis es investigar y ofrecer nuevas ideas para clasificar redes complejas basadas en sus propiedades topológicas de gran escala. Estamos interesados en estudiar las propiedades de redes de diferentes dominios, y encontrar características comunes que son compartidas por las redes en cada una de ellas. Con las mismas pretendemos desarrollar algoritmos y técnicas que aprovechen los elementos comunes, para automatizar la clasificación de redes en sus respectivos dominios. Esta información también será de utilidad para determinar si una red artificial presenta las características esperadas para el dominio al que pretende pertenecer. Revisamos un gran número de métricas de complejidad encontradas en la literatura. De ellas, elegimos 13 que luego derivan en un total de 43 métricas. Creamos un conjunto de redes de distintas fuentes, con 240 redes distribuidas en 11 dominios. Aplicamos un análisis exhaustivo a las medidas obtenidas para ellas, analizamos su correlación y distribución estadística, e intentamos predecir las posibilidades de clasificación que tendría un algoritmo automático a la hora de discriminarlas correctamente en sus respectivos dominios. Intentamos determinar si las mediciones obtenidas pueden ser usadas para discriminar los distintos dominios estudiados. Para ello, presentamos 3 tipos de algoritmos de clasificación de la literatura (K Nearest Neighbors, Support Vector Machines y el sistema de Evolutionary Rule Learning BioHEL). Las mediciones son utilizadas como valores de entrada para la tarea de clasificación de distinguir el dominio al que pertenece cada red. Además, para entender el potencial que tienen para clasificar dominios de redes, usamos el generador de grafos CiGRAM para crear un conjunto de 160 redes artificiales distribuidas en 8 dominios a modo de ejemplo. Analizamos su distribución estadística y ejecutamos los experimentos propuestos, donde algunos de los algoritmos logran una precisión de hasta 80%. Adicionalmente, observamos que es fácil interpretar los resultados que ofrece el sistema BioHEL, ya que su salida está compuesta de reglas legibles por una persona, que explican cómo clasificar redes en base a los valores de las métricas calculadas. Finalmente, aplicamos los experimentos propuestos usando las técnicas de clasificación revisadas, con los valores de métricas calculados para las redes reales elegidas. Observamos una clasificación de menor precisión con respecto a lo obtenido para las redes artificiales, y continuamos con escenarios experimentales adicionales para estudiar posibles mejoras, como eliminación de outliers y particionamiento manual de los conjunto de entrenamiento y prueba. Luego de ejecutarlos, a pesar de que en promedio los resultados siguen siendo peores a los obtenidos para las redes artificiales, un subconjunto de los experimentos presenta una precisión de 80% como habíamos obtenido anteriormente. Nuestras conclusiones permiten confirmar que es posible clasificar redes de distintos dominios considerando únicamente las mediciones obtenidas de un conjunto específico de métricas de complejidad, y también ofrecemos posibles mejoras a ser aplicadas en investigaciones futuras.

Abstract:
The objective of this thesis is to research and offer insights into the possibilities of classifying complex networks based on their large scale topological features. We are interested in studying the properties of networks from different domains, and find common characteristics that may be shared by the networks in each of them. With them, we aim to develop algorithms and techniques that take advantage of the shared features, to automate the classification of networks to their respective domains. This information would also be useful in determining if an artificial network shares the expected characteristics of its intended domain. We research and review a large number of complexity measures from the literature. From them, we choose 13 that are then derived to reach a total of 43 measures. We created a network data set from different sources, with 240 networks distributed across 11 domains. Exhaustive analysis is applied to the measurements obtained from them, to analyze their correlation and statistical distribution, and attempt to predict the classification possibilities an automated algorithm might have of correctly discriminating between the domains. We attempt to determine if the measures computed can be used as discriminators between the domains under study. To that end, we present 3 different classification algorithms from the literature (K Nearest Neighbors, Support Vector Machines and the Evolutionary Rule Learning system BioHEL). The measures obtained are used as the input for the classification task of distinguishing the domain to which each network belongs. Furthermore, to understand their potential ability to correctly classify network domains, we use the CiGRAM graph generator to build a set of 160 artificial networks distributed across 8 sample domains. We analyze their statistical distribution, and run the experiments proposed, where some of the algorithms presented achieve up to 80% accuracy. Moreover, we observe the ease of interpretation in the results offered by the BioHEL system, since its output is composed of human readable rules that explain how to classify the networks based on their computed measures. Finally, we apply the proposed experiments using the classification techniques reviewed to the computed measures of the set of real networks chosen. We observe a lower classification accuracy with regard to the values obtained for the artificial networks, and continue with additional experimental scenarios to study possible improvements, such as outlier elimination, and manual partitioning of the training and testing sets. After running them, we observe that despite the average results are still below those obtained for artificial networks, a subset of the experiments present the previously attained accuracy nearing 80%. Our conclusions imply that it is possible to classify networks into different domains just by considering the measurements obtained from a speciFinally, we apply the proposed experiments using the classification techniques reviewed to the computed measures of the set of real networks chosen. We observe a lower classification accuracy with regard to the values obtained for the artificial networks, and continue with additional experimental scenarios to study possible improvements, such as outlier elimination, and manual partitioning of the training and testing sets. After running them, we observe that despite the average results are still below those obtained for artificial networks, a subset of the experiments present the previously attained accuracy nearing 80%. Our conclusions imply that it is possible to classify networks into different domains just by considering the measurements obtained from a specific set of complexity measures, and we also offer a number of possible improvements in future related research.

http://digital.bl.fcen.uba.ar

Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34