Cops and Robbers on Graphs (C & R) is a vertex-to-vertex pursuit game played on graphs first introduced by Quilliot (in 1978) and Nowakowski (in 1983). The cop player starts the game by choosing a set of vertices which will be the cops’ starting positions. The robber player responds by choosing its own start vertex. On each player’s turn, the player may move its tokens to adjacent vertices. The cops win if the robber is captured (they occupy the same vertex). The robber wins if it can avoid capture indefinitely. The question, then, is to determine the smallest number of cops required to guarantee the robber will be captured. A variation of C & R called Zombies and Survivors (Z & S) was recently proposed and studied by Fitzpatrick. Z & S is the same as C & R with the added twist that the zombies are required to move closer to the survivor (by following a shortest path from the zombie to the survivor). Whenever multiple shortest paths exist, the zombies are free to choose which one to follow. As in C & R, we are interested in the minimum number of zombies required to guarantee the survivor will be caught. Chapter 1 summarizes important results in vertex-pursuit games. In Chapter 2 we give an example of a planar graph where 3 zombies always lose, whereas Aigner and Fromme showed in 1984 that three cops have a winning strategy on planar graphs. In Chapter 3 we show how two zombies can win on a cycle with one chord.

In today's network-dependent society, cyber attacks with network worms have become the predominant threat to confidentiality, integrity, and availability of network computing resources. Despite ongoing research efforts, there is still no comprehensive network-security solution aimed at controling large-scale worm propagation. The aim of this work is fivefold: (1) Developing an accurate combinatorial model of worm propagation that can facilitate the analysis of worm control strategies, (2) Building an accurate epidemiological model for the propagation of a worm employing local strategies, (3) Devising distributed architecture and algorithms for detection of worm scanning activities, (4) Designing effective control strategies against the worm, and (5) Simulation of the developed models and strategies on large, scale-free graphs representing real-world communication networks. The proposed pair-approximation model uses the information about the network structure--order, size, degree distribution, and transitivity. The empirical study of propagation on large scale-free graphs is in agreement with the theoretical analysis of the proposed pair-approximation model. We, then, describe a natural generalization of the classical cops-and-robbers game--a combinatorial model of worm propagation and control. With the help of this game on graphs, we show that the problem of containing the worm is NP-hard. Six novel near-optimal control strategies are devised: combination of static and dynamic immunization, reactive dynamic and invariant dynamic immunization, soft quarantining, predictive traffic-blocking, and contact-tracing. The analysis of the predictive dynamic traffic-blocking, employing only local information, shows that the worm can be contained so that 40\% of the network nodes are not affected. Finally, we develop the Detection via Distributed Blackholes architecture and algorithm which reflect the propagation strategy used by the worm and the salient properties of the network. Our distributed detection algorithm can detect the worm scanning activity when only 1.5% of the network has been affected by the propagation. The proposed models and algorithms are analyzed with an individual-based simulation of worm propagation on realistic scale-free topologies.

[pt] O objetivo desta dissertação é propor e aplicar um modelo conceitual para monitorar e avaliar projetos de pesquisa, desenvolvimento e inovação (PDeI) de novos produtos e sistemas complexos (CoPS), mediante o emprego de uma abordagem metodológica, que integra a escala Technology Readiness Level (TRL) à ferramenta Stage-Gate e emprega dois métodos multicritério de apoio à decisão. A metodologia compreende: (i) pesquisa bibliográfica e documental sobre os temas centrais da pesquisa; (ii) construção do modelo conceitual de monitoramento e avaliação (MA) de projetos de PD(e)I de CoPS de defesa, baseado na ferramenta Stage-Gate e na escala TRL; (iii) emprego do método Analytic Hierarchy Process (AHP) em dois momentos, sendo o primeiro para definir os pesos dos critérios para validação da qualidade dos indicadores de desempenho referentes a projetos de PD(e)I e o segundo para atribuir pesos aos critérios de avaliação dos referidos projetos no portões de decisão (gates); (iv) emprego do método TOPSIS para validação da qualidade dos indicadores de desempenho; e (v) aplicação do modelo proposto, tendo como foco um projeto de PD(e)I de CoPS em andamento no Centro Tecnológico do Exército (CTEx), visando evidenciar seu potencial de replicabilidade para os demais projetos de PD(e)I de CoPS daquele Centro. Destaca-se como resultado principal um modelo inovador de monitoramento e avaliação de projetos de PD(e)I de CoPS de defesa, que poderá ser aplicado no CTEx e em outras instituições de CT(e)I, que buscam a excelência em gestão da inovação, particularmente quando enfrentam os desafios do desenvolvimento de PD(e)I de CoPS. Os resultados do estudo empírico conduzido neste contexto organizacional mostraram que é possível empregar, de forma integrada e efetiva, a ferramenta Stage-Gate e a escala TRL para monitorar e avaliar projetos de PD(e)I de CoPS de defesa ao longo de seu desenvolvimento. / [en] The objective of this dissertation is to propose and apply a conceptual model for monitoring and evaluating research, development, and innovation (RDandI) projects of new complex products and systems (CoPS), using a methodological approach that integrates the Technology Readiness Level (TRL) scale with the Stage-Gate tool and employs two multicriteria decision support methods. The methodology comprises: (i) bibliographic and documentary research on the central themes of the research; (ii) development of the conceptual model for monitoring and evaluation RD(and)I projects of CoPS for the defense area, based on the Stage-Gate tool and the TRL scale; (iii) use of the Analytic Hierarchy Process (AHP) method in two moments, the first to define the weights of the criteria for validation of the quality of performance indicators related to RD(and)I projects; and the second to assign weights to the evaluation criteria for the mentioned projects at decision gates; (iv) use of the TOPSIS method to validate the quality of the performance indicators; and (v) application of the proposed model, focusing on an RD(and)I project underway at the Army Technological Center (CTEx), aiming to show its potential for replicability to other RD(and)I projects of CoPS at that Center. The main result is an innovative model for monitoring and evaluating RD(and)I projects of CoPS for the defense area, which can be applied at CTEx and other Science and Technology Institutions seeking excellence in innovation management, particularly when facing the challenges of CoPS development. The results of the empirical study conducted in this organizational context showed that it is possible to use the Stage-Gate tool and the TRL scale in an integrated and effective manner to monitor and evaluate RD(and)I projects of CoPS for the defense area throughout their development.

Cette thèse s'intéresse aux liens entre l'évolution du contenu en eau de l'atmosphère et la formation des précipitations. L'objectif général des travaux qui y sont présentés est d'améliorer la compréhension des mécanismes de formation des précipitations en se basant sur des mesures de vapeur d'eau effectuées principalement par GPS. Une étude statistique originale effectuée à partir de 5 années de mesures (GPS, pluviomètre et capteurs météorologiques au sol, situés sur le campus des Cézeaux, Clermont-Ferrand) a permis de mettre en évidence qu'en moyenne l'augmentation du contenu intégré en vapeur d'eau (IWV) est un précurseur de la formation des pluies, et que les variations de l'humidité dans la colonne atmosphérique toute entière sont pour l'essentiel découplées de celles observées à la surface. En effet, contrairement à l'humidité au sol, l'IWV atteint son maximum en moyenne 20 minutes avant le pic de précipitations. Cela semble indiquer que lorsque les précipitations commencent la condensation devient prépondérante à l'échelle de la colonne atmosphérique toute entière tandis qu'au niveau du sol il y a une forte évaporation. L'étude détaillée des précipitations convectives qui se sont produites sous le vent des Vosges le 18 Juillet 2007 (période d'observation intensive 9a de la campagne Convective and Orographically- induced Precipitation Study - COPS), a permis de mettre en évidence l'apport essentiel du GPS pour l'étude des précipitations convectives dans une région de moyenne montagne. En effet, grâce à une utilisation combinée de mesures radar à haute résolution, d'analyses de surface et de stations GPS (permettant d'observer des structures du champ de vapeur d'eau à petite échelle et haute résolution temporelle, à 2D et 3D), nous avons montré que l'accumulation d'humidité précédait de plusieurs heures l'initiation de la convection et que le déclenchement convectif est favorisé par la convergence du flux d'humidité. Cette dernière est associée à une convergence du vent dans les basses couches, ce qui entraîne un important transport vertical de la vapeur d'eau, observé grâce à la tomographie GPS. La direction du vent en amont du relief s'est révélée contrôler pour beaucoup la localisation des zones de convergence. Le forçage local dû à l'orographie à petite échelle (< 5km) a également été mis en évidence, en complétant les observations par des résultats de simulations numériques à haute résolution.

Moving target search has been given much attention during the last twenty years. It is a game in which multiple pursuers (cops) try to catch an evading agent (robber) and also known as the game of cops and robber. Within this thesis we study a discrete alternating version played on a graph with given initial positions for the cops and the robber, providing a number of results for optimal and sub-optimal approaches to the game.

No description available.

Popular Object Oriented size metrics and estimation methods are examined. A case study is conducted. Five of the methods (&ldquo / LOC&rdquo / , &ldquo / OOPS&rdquo / , &ldquo / Use Case Points Method&rdquo / , &ldquo / J.Kammelar&rsquo / s Sizing Approach&rdquo / and &ldquo / Mark II FP&rdquo / ) are applied to a project whose requirements are defined by means of use cases. Size and effort estimations are made and compared with the actual results of the project.

Title: Combinatorial Games Theory Author: Tomáš Valla Department / Institute: IUUK MFF UK Supervisor: Prof. RNDr. Jaroslav Nešetřil, DrSc., IUUK MFF UK Abstract: In this thesis we study the complexity that appears when we consider the competitive version of a certain environment or process, using mainly the tools of al- gorithmic game theory, complexity theory, and others. For example, in the Internet environment, one cannot apply any classical graph algorithm on the graph of connected computers, because it usually requires existence of a central authority, that manipu- lates with the graph. We describe a local and distributed game, that in a competitive environment without a central authority simulates the computation of the weighted vertex cover, together with generalisation to hitting set and submodular weight func- tion. We prove that this game always has a Nash equilibrium and each equilibrium yields the same approximation of optimal cover, that is achieved by the best known ap- proximation algorithms. More precisely, the Price of Anarchy of our game is the same as the best known approximation ratio for this problem. All previous results in this field do not have the Price of Anarchy bounded by a constant. Moreover, we include the results in two more fields, related to the complexity of competitive...

Cette thèse porte sur l’étude des propriétés structurelles de graphes dont la compréhension permet de concevoir des algorithmes efficaces pour résoudre des problèmes d’optimisation. Nous nous intéressons plus particulièrement aux méthodes de décomposition des graphes, aux jeux de poursuites et à la notion de convexité. Le jeu de Processus a été défini comme un modèle de la reconfiguration de routage. Souvent, ces jeux où une équipe de chercheurs doit effacer un graphe non orienté sont reliés aux décompositions de graphes. Dans les digraphes, nous montrons que le jeu de Processus est monotone et nous définissons une nouvelle décomposition de graphes que lui est équivalente. Ensuite, nous étudions d’autres décompositions de graphes. Nous proposons un algorithme FPT-unifiée pour calculer plusieurs paramètres de largeur de graphes. En particulier, ceci est le premier FPT-algorithme pour la largeur arborescente q-branché et spéciale d’un graphe. Nous étudions ensuite un autre jeu qui modélise les problèmes de pré-chargement. Nous introduisons la variante en ligne du jeu de surveillance. Nous étudions l’écart entre le jeu de surveillance classique et ses versions connecté et en ligne, en fournissant de nouvelles bornes. Nous définissons ensuite un cadre général pour l’étude des jeux poursuite-évasion. Cette méthode nous permet de donner les premiers résultats d’approximation pour certains de ces jeux. Finalement, nous étudions un autre paramètre lié à la convexité des graphes et à la propagation d’infection dans les réseaux, le nombre enveloppe. Nous fournissons plusieurs résultats de complexité en fonction des structures des graphes et en utilisant des décompositions de graphes. / This thesis focuses on the study of structural properties of graphs whose understanding enables the design of efficient algorithms for solving optimization problems. We are particularly interested in methods of decomposition, pursuit-evasion games and the notion of convexity. The Process game has been defined as a model for the routing reconfiguration problem in WDM networks. Often, such games where a team of searchers have to clear an undirected graph are closely related to graph decompositions. In digraphs, we show that the Process game is monotone and we define a new equivalent digraph decomposition. Then, we further investigate graph decompositions. We propose a unified FPT-algorithm to compute several graph width parameters. This algorithm turns to be the first FPT-algorithm for the special and the q-branched tree-width of a graph. We then study another pursuit-evasion game which models prefetching problems. We introduce the more realistic online variant of the Surveillance game. We investigate the gap between the classical Surveillance Game and its connected and online versions by providing new bounds. We then define a general framework for studying pursuit-evasion games, based on linear programming techniques. This method allows us to give first approximation results for some of these games. Finally, we study another parameter related to graph convexity and to the spreading of infection in networks, namely the hull number. We provide several complexity results depending on the graph structures making use of graph decompositions. Some of these results answer open questions of the literature.

En la present tesi doctoral s’han estudiat diversos mètodes per a l’eliminació de contaminants orgànics persistents en olis de peix amb finalitat alimentària. S’han posat al punt les metodologies d’anàlisi necessàries per a la correcta determinació d’aquests compostos en la matriu d’estudi. S’han avaluat amb detall les etapes de purificació de la mostra, fraccionament dels analits i anàlisi instrumental. El mètode ha estat validat amb resultats satisfactoris, i s’ha comprovat el seu bon funcionament a través de la participació en diversos exercicis d’intercalibtage, així com la realització de diversos estudis amb mostres reals d’oli de peix. S’ha estudiat l’eliminació dels contaminants orgànics persistents a través d’adsorbents sòlids amb base silícica i carbonàcia. Les condicions experimentals han estat estudiades més a fons mitjançant dissenys d’experiències, per acabar optimitzant el mètode d’adsorció amb un disseny d’evolució. Els millors resultats s’han obtingut amb el carbó actiu, que mostra una elevada eficàcia en l’eliminació de PCDD/Fs, d-l PCBs i HCB. S’ha estudiat l’eliminació dels contaminants orgànics persistents mitjançant tècniques de degradació fotoquímiques. Inicialment s’ha fotodegradat cada família de contaminants per separat, per poder estudiar més a fons les condicions necessàries per la seva eliminació, així com els seus mecanismes i productes de degradació. Posteriorment s’ha estudiat la fotodegradació simultània dels analits d’interès en oli de peix. Aquesta tècnica s’ha mostrat efectiva en l’eliminació de DDT, PBDEs, HCB i PCBs similars a dioxines. Paral•lelament als estudis d’eliminació mitjançant adsorbents sòlids i tècniques fotoquímiques, s’ha comprovat la qualitat dels olis de peix abans i després del tractament. El procés d’adsorció en sòlids no afecta significativament a la qualitat de l’oli, mentre que les tècniques fotoquímiques degraden una part dels àcids grassos insaturats. S’ha estudiat l’eliminació de contaminants orgànics persistents en oli de peix mitjançant la combinació de les dues tècniques estudiades anteriorment, amb una primera etapa de degradació fotoquímica i una segona etapa d’adsorció. S’han comparat els resultats finals d’eliminació que s’obtenen amb cada un dels mètodes desenvolupats (adsorció, fotodegradació i combinat). L’adsorció en carbó actiu és el procés més adequat per l’eliminació de COPs en oli de peix. S’ha realitzat un estudi dels nivells diastereomèrics i enantiomèrics d’un contaminant emergent -l’hexabromociclododecà (HBCD)- en oli de peix. S’ha avaluat la seva eliminació de la matriu d’estudi mitjançant adsorbents amb base carbonàcia i degradació fotoquímica, sent principalment eliminat per aquesta segona via. / En la presente tesis doctoral se han estudiado diversos métodos para la eliminación de contaminantes orgánicos persistentes en aceites de pescado con finalidad alimentaria. Se han desarrollado los métodos de análisis necesarios para la correcta determinación de estos compuestos en la matriz de estudio. Se han evaluado con detalle las etapas de purificación de la muestra, fraccionamiento de los analitos y análisis instrumental. El método ha sido validado con resultados satisfactorios, y se ha comprobado su buen funcionamiento mediante ejercicios de intercalibraje, así como la realización de diversos estudios con muestras reales de aceite de pescado. Se ha estudiado la eliminación de los contaminantes persistentes mediante adsorbentes sólidos con base silícica y carbonacea. Las condiciones experimentales han estado estudiadas en profundidad mediante diseños de experiencias y de evolución. Los mejores resultados se han obtenido con carbón activo, que demuestra una elevada eficacia en la eliminación de PCDD/Fs, dl-PCBs y HCB. Se ha estudiado la eliminación de los contaminantes orgánicos persistentes mediante técnicas de degradación fotoquímica. Inicialmente se ha fotodegradado cada familia de contaminantes por separado, para poder estudiar más a fondo las condiciones necesarias para su eliminación. Posteriormente se ha estudiado la degradación simultánea de los analitos de interés en aceite de pescado. Esta técnica se ha mostrado efectiva en la eliminación de DDT, PBDEs, HCB y PCBs similares a dioxinas. Paralelamente a los estudios de eliminación mediante adsorbentes sólidos y técnicas fotoquímicas, se ha comprobado la calidad de los aceites de pescado antes y después del tratamiento. El proceso de adsorción en sólidos no afecta significativamente a la calidad del aceite, mientras que las técnicas fotoquímicas degradan una parte de los ácidos grasos insaturados. Se ha estudiado la eliminación de contaminantes orgánicos persistentes en aceites de pescado mediante la combinación de las dos técnicas estudiadas anteriormente, con una primera etapa de degradación fotoquímica y una segunda etapa de adsorción. Se han comparado los resultados finales de eliminación que se obtienen con cada uno de los métodos desarrollados. La adsorción en carbón activo es el proceso más adecuado para la eliminación de COPs en aceite de pescado. Se ha realizado un estudio de los niveles diastereoisoméricos y enantioméricos de un contaminante emergente –HBCD- en aceite de pescado. Se ha evaluado su capacidad de eliminación de la matriz de estudio mediante adsorbentes con base carbonacia y degradación fotoquímica, siendo principalmente eliminado por la segunda vía. / During the present doctoral thesis several methods for the elimination of persistent organic pollutants from fish oil have been studied. Analytical methodologies for the determination of these compounds in fish oil have been developed. Sample purification, fractionation of the analytes and instrumental determination steps have been deeply studied. The method has been validated with satisfactory results, and its performance has been verified through its participation in several intercalibration exercises and studies with real fish oil samples. Elimination of persistent organic pollutants with silicon and carbon-based adsorbents has been studied. The experimental conditions have been studied in depth with an experimental design, to finally optimize the adsorption method using an evolutionary design. Best results have been obtained with the active carbon, showing high efficiency of the removal of PCDD/Fs, dioxin-like PCBs and HCB. Elimination of persistent organic pollutants with photochemical degradation techniques has been studied. Initially, each family of pollutants has been photodegraded separately, to determine its degradation conditions, as well as degradation mechanisms and by-products. Later, simultaneous photodegradation of the analytes has been studied in fish oil. This technique has shown high efficiency on the degradation of DDT, PBDEs, HCB and dioxin-like PCBs. The quality of the oils before and after the treatments with solid adsorbents and photochemical degradation has also been studied. The adsorption process does not significantly affect the quality of the oils, while photochemical techniques can degrade the unsaturated fatty acids. Elimination of persistent organic pollutants in fish oil combining adsorption in solids and photochemical degradation has been studied. Results obtained with each of the developed methodologies (adsorption, photodegradation and combined method) were compared. Adsorption in active carbon is the most suitable process for COPs elimination in fish oil. Finally, diastereoisomeric and enantiomeric levels of an emerging pollutant –hexabromocyclododecane (HBCD)- in fish oil have been studied. Its elimination has been evaluated with carbon-based adsorbents and photochemical degradation, being mainly eliminated with the photodegradation techniques.