Cette thèse porte sur des aspects structuraux et algorithmiques des graphes. Elle est divisée en deux parties, qui comportent deux études différentes : une partie sur des algorithmes centralisés-séquentiels, et une autre sur des algorithmes distribués. Dans la première partie, on étudie des aspects algorithmiques de deux structures de graphes appelés séparateurs minimaux et cliques maximales potentielles. Ces deux objets sont au coeur d'un méta-théorème dû à Fomin, Todinca and Villanger (SIAM J. Comput. 2015), qui affirme qu'une grande famille des problèmes d'optimisation peut être résolue en temps polynomial, si le graphe d'entrée contient un nombre polynomial de séparateurs minimaux. La contribution de cette partie consiste à prolonger le méta-théorème de Fomin et al. de deux manières : d'un côté, on l'adapte pour qu'il soit valide pour une plus grande famille des problèmes ; de l'autre, on étend ces résultats à des version paramétrées, pour certains paramètres des graphes. La deuxième partie de la thèse correspond à une étude du modèle appelé « Diffusion dans une Clique Congestionnée ». Dans ce modèle, les sommets d'un graphe communiquent entre eux dans des rondes synchrones, en diffusant un message de petite taille, visible par tout autre sommet. L'objectif ici est d'élaborer des protocoles qui reconnaissent des classes de graphes, en minimisant la taille des messages et le nombre de rondes. La contribution de cette partie est l'étude du rôle du hasard dans ce modèle, et la conception de protocoles pour la reconnaissance et la reconstruction des certaines classes des graphes. / This thesis is about structural and algorithmic aspects of graphs. It is divided in two parts, which are about two different studies: one part is about centralized-sequential algorithms, and the other part is about distributed algorithms. In the first part of the thesis we study algorithmic applications of two graph structures called minimal separators and potential maximal cliques. These two objects are in the core of a meta-theorem due to Fomin, Todinca and Villanger (SIAM J. Comput. 2015), which states that a large family of graph optimization problems can be solved in polynomial time, when the input is restricted to the family of graphs with polynomially many minimal separators. The contribution of this part of the thesis is to extend the meta-theorem of Fomin et al. in two ways. On one hand, we adapt it to be valid into a larger family of problems. On the other hand, we extend it into a parameterized version, for several graph parameters. In the second part of this thesis we study the broadcast congested clique model. In this model, the nodes of a graph communicate in synchronous rounds, broadcasting a message of small size visible to every other node. The goal is to design protocols that recognize graph classes minimizing the number of rounds and the message sizes. The contribution of this part is to explore the role of randomness on this model, and provide protocols for the recognition and reconstruction of some graph classes.

O objetivo da presente dissertação foi verificar o efeito da participação de jovens jogadores de futebol em competições com calendário congestionado (CC) nas medidas de desempenho físico, e comparar as acelerações (ACC), as desacelerações (DEC), a potência metabólica média (PM), distância total percorrida (DT) e distância percorrida em alta velocidade (DAV) em 24 jogadores de futebol juvenil (sub-15, n = 11 e sub-17, n = 13) expostos a campeonatos de CC e períodos regulares de calendário não congestionados (calendário regular; CR); como critério de retenção dos dados dos jogadores, adotou-se, a participação mínima de 75% do tempo total de jogo em cada partida. Adicionalmente as medidas de desempenho físico foram normalizadas pelo tempo de participação em minutos na partida. Foram analisados 10 jogos internacionais no formato de CC (5 para cada categoria), realizados durante 3 dias sucessivos, incluindo 2 dias com 2 jogos consecutivos jogados com intervalo de 4-5 horas; para estabelecer uma condição \"controle\", 10 jogos de CR, de cada categoria, foram analisados; os jogos de CR foram realizados com um intevalo de pelo menos 7 dias. Os jogadores usavam uma unidade GPS de 15 Hz com um acelerômetro triaxial de 100 Hz alocada em uma veste especial. Uma diferença classificada como digna de consideração (tamanho do efeito; TE> 0,20) entre CC e CR, foi observada para os parâmetros de desempenho físico ACC, DEC e PM, para sub-15 e sub-17, com valores mais elevados no CC. Enquanto que DT e DAV apresentaram valores superiores para CR, apenas para o sub-15. Contrariamente à hipótese levantada, os parâmetros de desempenho físico mostram que os jogadores juvenis de elite avaliados elevaram a intensidade do jogo quando participaram de torneio CC. Uma diminuição em ACC e DEC, do 1° tempo para o 2° tempo foi observada (sub-15 e sub-17) nos diferentes formatos de campeonato. No entanto, observou-se um aumento da PM do 1° tempo para o 2° tempo; com um aumento muito grande para ambas as categorias durante a CR; para o CC, a PM aumentou (1ª para a 2ª metade) para o sub-17, mas diminuiu para o sub-15. Os resultados do presente estudo, sugerem que os perfis de taxa de trabalho dos jogadores não são prejudicados no CC e que o desempenho físico aumentado nesse tipo de competição pode estar associado a uma estratégia de auto-regulação ou \"pacing\" da intensidade de realização das ações. Apesar das semelhanças para os dados de desempenho físico (sub-15 e sub-17), a PM para o sub-17 foi amplamente aumentada no CC (vs CR) em comparação com os valores de PM do sub-15; sugerindo assim, uma maior capacidade dos atletas, com um suposto nível mais elevado de treinamento (sub-17) em otimizar o desempenho físico neste tipo de competição. Estas informações podem servir como um meio alternativo e eficiente de representação do desempenho físico e auxiliar na organização de uma preparação específica de equipes participantes destes formatos de competições (CC); adicionalmente, os resultados indicam a importância de de considerar as medidas de ACC, DEC e PM na análise do desempenho físico de jovens jogadores, ao invés da utilização isolada de medidas relacionadas a DT e DAV / The aim of this study was to compare the physical performances in youth players during congested (CM) versus regular match (RM) schedules. The accelerations (ACC), decelerations (DEC), average metabolic power (MP), total distance covered (TD) and distance covered at high speed (HSD) were compared across congested match (CM; 10 international matches played over 3 successive days, including 2 days with 2 consecutive matches played with a 4-5 hr interval) and 10 regular non-congested match periods (RM), played with a 7-day interval between matches, in elite youth soccer players (U15, n=11; U17, n=13).; as criterion for retention of the players\' data, it was adopted, the minimum participation of 75% of the total match time of each game. In addition, all variables were normalized per min of on-field playing time. Each player wore a 15-Hz GPS unit coupled with a 100 Hz tri-axial accelerometer (SPI Elite, GPSports, Canberra, Australia A difference classified as worthy of consideration (effect size; ES > 0.20), between CM and RM, was observed for ACC, DEC and MP, for U15 and U17, with higher values in CM. While TD and HSD showed lower values for CM for u15. Contrary to the hypothesis, the relative values of the physical performance parameters were higher for CM. A decrease in ACC and DEC, from the 1st half to the 2nd half of the match was observed (U15 and U17) for both CM and RM. However, an increase in MP from the 1st half to the 2nd half of the match was observed; with a very large increase for both categories during the RM; during the CM, MP increased (1st half to the 2nd half) in the U7, but decreased in U15. The present findings suggest that the players work rate profiles are not impaired in CM and that the intensity of the match-play is increased in this type of competition, and might be associated to self-regulation or pacing strategy; despite the similarities for physical performance in U15 and U17), MP was largely increased in U17 during CM (vs CR) compared to U15; this result suggests that the higher the level of the conditioning, the greater the ability of the athlete in optimizing physical performance in this type of match schedule. This information can serve as an alternative and efficient means of representing physical performance and may help coaches to organize and monitor specific preparations of teams participating in these type of competitions (CM); additionally, the results indicate the importance of considering the ACC, DEC and MP measurements in the analysis of physical performance of young players, instead of using only measures related to total distance covered and distances covered at different speeds

In recent years European airspace has become increasingly congested and airlines can now observe that en-route capacity constraints are the fastest growing source of flight delays. In 2010 this source of delay accounted for 19% of all flight delays in Europe and has been increasing with an average yearly rate of 17% from 2005 to 2010. This paper suggests and evaluates an approach to how disruption management can be combined with flight planning in order to create more proactive handling of the kind of disruptions, which are caused by congested airspace. The approach is evaluated using data from a medium size European carrier and estimates a lower bound saving of several million USD.

Anotation: This thesis deals with leisure activities of children of preschool age and children of school age and it is trying to discover their favorite activities and interests, regularly visited leisure and quantity of it. The theoretical part deals with terms as free time, family, child of preschool age and child of school age, education in free time. It also deals with overloaded children and with problems associated with overloading. The aim of this thesis is the evaluation and analysis how children of preschool age and children of school age spending their free time. Through research questions we were trying to find out how children spend their free time and how many aktivities do they have in their free time. The empirical part contains the analysis of used methods , research investigation in the kindergarten and primary school in Martin. It also includes treatment of results - Its processed in tables, graphs and written comments.

Neste trabalho é proposto um método de carregamento incremental dos fluxos veiculares para a estimação de matriz O-D sintética. A principal motivação para o desenvolvimento deste trabalho está na complexidade dos métodos de estimação de matriz sintética pelo método iterativo, que tem conduzido a resultados não satisfatórios. O método de carregamento incremental, ora proposto neste trabalho, pode ser definido como o inverso do método de alocação incremental de viagens aos arcos de uma rede viária. A matriz O-D obtida com este método é o resultado da soma sucessiva das sub-matrizes estimadas através das parcelas dos fluxos observados nos arcos da rede. Este método pode ser aplicado em qualquer tipo de rede viária: congestionada ou não congestionada e com ou sem continuidade de fluxo. Para verificação do desempenho do método foram realizados testes experimentais, nos quais os resultados obtidos foram comparados com os valores observados. O desempenho do método incremental não se mostrou satisfatório. Assim, com o intuito de verificar a sua utilidade como um método alternativo os mesmos dados foram processados através de dois métodos iterativos. Os resultados mostraram que os erros são ainda maiores do que os obtidos pelo método proposto. A principal conclusão deste trabalho é que o método incremental pode ser usado como uma alternativa aos métodos iterativos. / A synthetic O-D matrix estimation method, based on incremental loading of traffic flow, was proposed in this work. This research was motivated because of the complexity of the iterative methods for synthetic matrix estimation that might produce bias accumulation in the results. The referred incremental loading method could be defined as the inverse of the incremental assignment method for trips to links of a traffic network. The O-D matrix is gathered by successively summing the sub-matrices obtained from parts of the traffic flow counted on the links of the traffic network. This method could be applied to any traffic networks: congested or uncongested and with or without volumetric continuity. As a part of verification proceeding, several experimental tests were carried out to evaluate the method performance. In these tests the estimated results were compared with the real values. These results show that the incremental loading method performance was not satisfactory. Thus, aiming to test the utility of the incremental method, a second round of experimental tests was conducted to evaluate two iterative methods. In these second round tests, the results show that theses methods performance was worse those of the incremental method. The main conclusion of this work is that the incremental loading method for synthetic matrices estimation could be used as an alternative to the iterative methods.

Neste trabalho é proposto um método de carregamento incremental dos fluxos veiculares para a estimação de matriz O-D sintética. A principal motivação para o desenvolvimento deste trabalho está na complexidade dos métodos de estimação de matriz sintética pelo método iterativo, que tem conduzido a resultados não satisfatórios. O método de carregamento incremental, ora proposto neste trabalho, pode ser definido como o inverso do método de alocação incremental de viagens aos arcos de uma rede viária. A matriz O-D obtida com este método é o resultado da soma sucessiva das sub-matrizes estimadas através das parcelas dos fluxos observados nos arcos da rede. Este método pode ser aplicado em qualquer tipo de rede viária: congestionada ou não congestionada e com ou sem continuidade de fluxo. Para verificação do desempenho do método foram realizados testes experimentais, nos quais os resultados obtidos foram comparados com os valores observados. O desempenho do método incremental não se mostrou satisfatório. Assim, com o intuito de verificar a sua utilidade como um método alternativo os mesmos dados foram processados através de dois métodos iterativos. Os resultados mostraram que os erros são ainda maiores do que os obtidos pelo método proposto. A principal conclusão deste trabalho é que o método incremental pode ser usado como uma alternativa aos métodos iterativos. / A synthetic O-D matrix estimation method, based on incremental loading of traffic flow, was proposed in this work. This research was motivated because of the complexity of the iterative methods for synthetic matrix estimation that might produce bias accumulation in the results. The referred incremental loading method could be defined as the inverse of the incremental assignment method for trips to links of a traffic network. The O-D matrix is gathered by successively summing the sub-matrices obtained from parts of the traffic flow counted on the links of the traffic network. This method could be applied to any traffic networks: congested or uncongested and with or without volumetric continuity. As a part of verification proceeding, several experimental tests were carried out to evaluate the method performance. In these tests the estimated results were compared with the real values. These results show that the incremental loading method performance was not satisfactory. Thus, aiming to test the utility of the incremental method, a second round of experimental tests was conducted to evaluate two iterative methods. In these second round tests, the results show that theses methods performance was worse those of the incremental method. The main conclusion of this work is that the incremental loading method for synthetic matrices estimation could be used as an alternative to the iterative methods.

A model for estimating travel time on short arterial links of congested urban networks, using currently available technology, is introduced in this thesis. The objective is to estimate travel time, with an acceptable level of accuracy for real-life traffic problems, such as congestion management and emergency evacuation. To achieve this research objective, various travel time estimation methods, including highway trajectories, multiple linear regression (MLR), artificial neural networks (ANN) and K –nearest neighbor (K-NN) were applied and tested on the same dataset. The results demonstrate that ANN and K-NN methods outperform linear methods by a significant margin, also, show particularly good performance in detecting congested intervals. To ensure the quality of the analysis results, set of procedures and algorithms based on traffic flow theory and test field information, were introduced to validate and clean the data used to build, train and test the different models.

Cette thèse est dédiée à l'étude mathématique de quelques modèles de trafic routier congestionné. La notion essentielle est l'équilibre de Wardrop. Elle poursuit des travaux de Carlier et Santambrogio avec des coauteurs. Baillon et Carlier ont étudié le cas de grilles cartésiennes dans $\RR^2$ de plus en plus denses, dans le cadre de la théorie de $\Gamma$-convergence. Trouver l'équilibre de Wardrop revient à résoudre des problèmes de minimisation convexe. Dans le chapitre 2, nous regardons ce qui se passe dans le cas de réseaux généraux, de plus en plus denses, dans $\RR^d$. Des difficultés nouvelles surgissent par rapport au cas initial de réseaux cartésiens et pour les contourner, nous introduisons la notion de courbes généralisées. Des hypothèses structurelles sur ces suites de réseaux discrets sont nécessaires pour s'assurer de la convergence. Cela fait alors apparaître des fonctions qui sont des sortes de distances de Finsler et qui rendent compte de l'anisotropie du réseau. Nous obtenons ainsi des résultats similaires à ceux du cas cartésien. Dans le chapitre 3, nous étudions le modèle continu et en particulier, les problèmes limites. Nous trouvons alors des conditions d'optimalité à travers une formulation duale qui peut être interprétée en termes d'équilibres continus de Wardrop. Cependant, nous travaillons avec des courbes généralisées et nous ne pouvons pas appliquer directement le théorème de Prokhorov, comme cela a été le cas dans \cite{baillon2012discrete, carlier2008optimal}. Pour pouvoir néanmoins l'utiliser, nous considérons une version relaxée du problème limite, avec des mesures d'Young. Dans le chapitre 4, nous nous concentrons sur le cas de long terme, c'est-à-dire, nous fixons uniquement les distributions d'offre et de demande. Comme montré dans \cite{brasco2013congested}, le problème de l'équilibre de Wardrop est équivalent à un problème à la Beckmann et il se réduit à résoudre une EDP elliptique, anisotropique et dégénérée. Nous utilisons la méthode de résolution numérique de Lagrangien augmenté présentée dans \cite{benamou2013augmented} pour proposer des exemples de simulation. Enfin, le chapitre 5 a pour objet l'étude de problèmes de Monge avec comme coût une distance de Finsler. Cela se reformule en des problèmes de flux minimal et une discrétisation de ces problèmes mène à un problème de point-selle. Nous le résolvons alors numériquement, encore grâce à un algorithme de Lagrangien augmenté. / This thesis is devoted to the mathematical analysis of some models of congested road traffic. The essential notion is the Wardrop equilibrium. It continues Carlier and Santambrogio's works with coauthors. With Baillon they studied the case of two-dimensional cartesian networks that become very dense in the framework of $\Gamma$-convergence theory. Finding Wardrop equilibria is equivalent to solve convex minimisation problems.In Chapter 2 we look at what happens in the case of general networks, increasingly dense. New difficulties appear with respect to the original case of cartesian networks. To deal with these difficulties we introduce the concept of generalized curves. Structural assumptions on these sequences of discrete networks are necessary to obtain convergence. Sorts of Finsler distance are used and keep track of anisotropy of the network. We then have similar results to those in the cartesian case.In Chapter 3 we study the continuous model and in particular the limit problems. Then we find optimality conditions through a duale formulation that can be interpreted in terms of continuous Wardrop equilibria. However we work with generalized curves and we cannot directly apply Prokhorov's theorem, as in \cite{baillon2012discrete, carlier2008optimal}. To use it we consider a relaxed version of the limit problem with Young's measures. In Chapter 4 we focus on the long-term case, that is, we fix only the distributions of supply and demand. As shown in \cite{brasco2013congested} the problem of Wardrop equilibria can be reformulated in a problem à la Beckmann and reduced to solve an elliptic anisotropic and degenerated PDE. We use the augmented Lagrangian scheme presented in \cite{benamou2013augmented} to show a few numerical simulation examples. Finally Chapter 5 is devoted to studying Monge problems with as cost a Finsler distance. It leads to minimal flow problems. Discretization of these problems is equivalent to a saddle-point problem. We then solve it numerically again by an augmented Lagrangian algorithm.