The changing topology of a network is driven by the need to maintain or optimize network function. As this function is often related to moving quantities such as traffic, information, etc., efficiently through the network, the structure of the network and the dynamics on the network directly depend on the other. To model this interplay of network structure and dynamics we use the dynamics on the network, or the dynamical processes the network models, to influence the dynamics of the network structure, i.e., to determine where and when to modify the network structure. We model the dynamics on the network using Jackson network dynamics and the dynamics of the network structure using minimal specialization, a variant of the more general network growth model known as specialization. The resulting model, which we refer to as the integrated specialization model, coevolves both the structure and the dynamics of the network. We show this model produces networks with real-world properties, such as right-skewed degree distributions, sparsity, the small-world property, and non-trivial equitable partitions. Additionally, when compared to other growth models, the integrated specialization model creates networks with small diameter, minimizing distances across the network. Along with producing these structural features, this model also sequentially removes the network's largest bottlenecks. The result are networks that have both dynamic and structural features that allow quantities to more efficiently move through the network.

Title: Parameterized Complexity Author: Ondřej Suchý Department: Department of Applied Mathematics Advisor: Prof. RNDr. Jan Kratochvíl, CSc. Advisor's e-mail address: honza@kam.mff.cuni.cz Abstract: This thesis deals with the parameterized complexity of NP-hard graph problems. We explore the complexity of the problems in various scenarios, with respect to miscellaneous parameters and their combina- tions. Our aim is rather to classify in this multivariate manner whether the particular parameters make the problem fixed-parameter tractable or intractable than to present the algorithm achieving the best running time. In the questions we study typically the first-choice parameter is unsuccessful, in which case we propose to use less standard ones. The first family of problems investigated provides a common general- ization of many well known and studied domination and independence problems. Here we suggest using the dual parameterization and show that, in contrast to the standard solution-size, it can confine the in- evitable combinatorial explosion. Further studied problems are ana- logues of the Steiner problem in directed graphs. Here the parameter- ization by the number of terminals to be connected seems to be previ- ously unexplored in the directed setting. Unfortunately, the problems are shown to be...

Cette thèse est composée de deux parties : l’une traite des propriétés combinatoires de mots infinis et l’autre des problèmes de colorations des graphes.La première partie du manuscrit concerne les structures régulières dans les mots apériodiques infinis, à savoir les sous-séquences arithmétiques et les premiers retours complets.Nous étudions la fonction qui donne la longueur maximale d’une sous-séquence arithmétique monochromatique (une progression arithmétique) en fonction de la différence commune d pour une famille de mots morphiques uniformes, qui inclut le mot de Thue-Morse. Nous obtenons la limite supérieure explicite du taux de croissance de la fonction et des emplacements des progressions arithmétiques de longueurs maximales et de différences d. Pour étudier des sous-séquences arithmétiques périodiques dans des mots infinis, nous définissons la notion d'indice arithmétique et obtenons des bornes supérieures et inférieures sur le taux de croissance de la fonction donnant l’indice arithmétique dans la même famille de mots.Dans la même veine, une autre question concerne l’étude de deux nouvelles fonctions de complexité de mots infinis basées sur les notions de mots ouverts et fermés. Nous dérivons des formules explicites pour les fonctions de complexité ouverte et fermée pour un mot d'Arnoux-Rauzy sur un alphabet de cardinalité finie.La seconde partie de la thèse traite des colorations parfaites (des partitions équitables) de graphes infinis de degré borné. Nous étudions les graphes de Caley de groupes additifs infinis avec un ensemble de générateurs fixé. Nous considérons le cas où l'ensemble des générateurs est composé d'entiers de l'intervalle [-n, n], et le cas où les générateurs sont des entiers impairs de [-2n-1, 2n+1], où n est un entier positif. Pour les deux familles de graphes, nous obtenons une caractérisation complète des colorations parfaites à deux couleurs / The content of the thesis is comprised of two parts: one deals with combinatorial properties of infinite words and the other with graph coloring problems.The first main part of the manuscript concerns regular structures in infinite aperiodic words, such as arithmetic subsequences and complete first returns.We study the function that outputs the maximal length of a monochromatic arithmetic subsequence (an arithmetic progression) as a function of the common difference d for a family of uniform morphic words, which includes the Thue-Morse word. We obtain the explicit upper bound on the rate of growth of the function and locations of arithmetic progressions of maximal lengths and difference d. To study periodic arithmetic subsequences in infinite words we define the notion of an arithmetic index and obtain upper and lower bounds on the rate of growth of the function of arithmetic index in the same family of words.Another topic in this direction involves the study of two new complexity functions of infinite words based on the notions of open and closed words. We derive explicit formulae for the open and closed complexity functions for an Arnoux-Rauzy word over an alphabet of finite cardinality.The second main part of the thesis deals with perfect colorings (a.k.a. equitable partitions) of infinite graphs of bounded degree. We study Caley graphs of infinite additive groups with a prescribed set of generators. We consider the case when the set of generators is composed of integers from the interval [-n,n], and the case when the generators are odd integers from [-2n-1,2n+1], where n is a positive integer. For both families of graphs, we obtain a complete characterization of perfect 2-colorings