The total domination number γt(G) of a graph G is the minimum cardinality of a set S of vertices, so that every vertex of G is adjacent to a vertex in S. In this article, we determine an optimal upper bound on the total domination number of a graph with diameter 2. We show that for every graph G on n vertices with diameter 2, γt(G)≤1+nln(n). This bound is optimal in the sense that given any ε>0, there exist graphs G with diameter 2 of all sufficiently large even orders n such that γt(G)>(14+ε)nln(n).

Sensor network coverage refers to the quality of service provided by a sensor network surveilling a region of interest. So far, coverage problems have been formulated to address area coverage or to maintain line-of-sight visibility in the presence of obstacles (i.e., art-gallery problems). Although very useful in many sensor applications, none of the existing formulations address coverage as it pertains to target tracking by means of multiple sensors, nor do they provide a closed-form function that can be applied to the problem of allocating sensors for the surveilling objective of maximizing target detection while minimizing false alarms. This dissertation presents a new coverage formulation addressing the quality of service of sensor networks that cooperatively detect targets traversing a region of interest, and is readily applicable to the current sensor network coverage formulations. The problem of track coverage consists of finding the positions of <em>n</em> sensors such that the amount of tracks detected by at least <em>k</em> sensors is optimized. This dissertation studies the geometric properties of the network, addressing a deterministic track-coverage formulation and binary sensor models. It is shown that the tracks detected by a network of heterogeneous omnidirectional sensors are the geometric transversals of non-translates families of disks. A novel methodology based on cones and convex analysis is presented for representing and measuring sets of transversals as closed-form functions of the sensors positions and ranges. As a result, the problem of optimally deploying a sensor network with the aforementioned objectives can be formulated as an optimization problem subject to mission dynamics and constraints. The sensor placement problem, in which the sensors are placed such that track coverage is maximized for a fixed sensor network, is formulated as a nonlinear program and solved using sequential quadratic programming. The sensor deployment, involving a dynamic sensor network installed on non-maneuverable sonobuoys deployed in the ocean, is formulated as an optimization problem subject to inverse dynamics. Both a finite measure of the cumulative coverage provided by a sensor network over a fixed period of time and the oceanic-induced current velocity field are accounted for in order to optimize the dynamic sensor network configuration. It is shown that a state-space representation of the motions of the individual sensors subject to the current vector field can be derived from sonobuoys oceanic drift models and obtained from CODAR measurements. Also considered in the sensor model are the position-dependent acoustic ranges of the sensors due to the effects from heterogenous environmental conditions, such as ocean bathymetry, surface temporal variability, and bottom properties. A solution is presented for the initial deployment scheme of the non-maneuverable sonobuoys subject to the ocean's current, such that sufficient track coverage is maintained over the entire mission. As sensor networks are subject to random disturbances due to unforseen heterogenous environmental conditions propagated throughout the sensors trajectories, the optimal initial positions solution is evaluated for robustness through Monte Carlo simulations. Finally, the problem of controlling a network of maneuverable underwater vehicles, each equipped with an onboard acoustic sensor is formulated using optimal control theory. Consequently, a new optimal control problem is presented that integrates sensor objectives, such as track coverage, with cooperative path planning of a mobile sensor network subject to time-varying environmental dynamics. / Dissertation

Neste trabalho, apresentamos um método algébrico para obter formas normais de campos vetoriais reversíveis equivariantes. Adaptamos o método clássico de Belitskii-Elphick, usando ferramentas da teoria invariante para estabelecer fórmulas que consideram as simetrias e antissimetrias como ponto de partida. Mostramos que este método, mesmo sem simetrias, possui uma estreita relação com o método da transversal completa da teoria de singularidades. Com as ferramentas desenvolvidas nesta tese, a forma normal obtida e uma série formal que não depende do cálculo do kernel do chamado operador homológico. Formas normais para duas classes de campos, ressonantes e não ressonantes, são apresentadas, para diferentes representações do grupo \'Z IND. 2\' x \'Z IND. 2\' cuja linearização tem uma parte nilpotente de dimensão 2 e uma parte semi-simples com autovalores puramente imaginários / We give an algebraic method to obtain normal forms of reversible equivariant vector fields. We adapt the classical method by Belitskii-Elphick using tools from invariant theory to establish formulae that take symmetries into account as a starting point. We show that this method, even without symmetries, has a close relation to complete transversal of singularities theory. Applying the method developed in this thesis, the resulting normal form is a formal series which does not depend of the computation of the kernel of the so called homologic operator. Normal forms of two classes of non-resonant and resonant cases are presented, for dierent representations of the group \'Z INT. 2\' x \'Z INT. 2\' - with linearization having a 2 - dimensional nilpotent part and a semisimple part with purely imaginary eigenvalues

Neste trabalho, apresentamos um método algébrico para obter formas normais de campos vetoriais reversíveis equivariantes. Adaptamos o método clássico de Belitskii-Elphick, usando ferramentas da teoria invariante para estabelecer fórmulas que consideram as simetrias e antissimetrias como ponto de partida. Mostramos que este método, mesmo sem simetrias, possui uma estreita relação com o método da transversal completa da teoria de singularidades. Com as ferramentas desenvolvidas nesta tese, a forma normal obtida e uma série formal que não depende do cálculo do kernel do chamado operador homológico. Formas normais para duas classes de campos, ressonantes e não ressonantes, são apresentadas, para diferentes representações do grupo \'Z IND. 2\' x \'Z IND. 2\' cuja linearização tem uma parte nilpotente de dimensão 2 e uma parte semi-simples com autovalores puramente imaginários / We give an algebraic method to obtain normal forms of reversible equivariant vector fields. We adapt the classical method by Belitskii-Elphick using tools from invariant theory to establish formulae that take symmetries into account as a starting point. We show that this method, even without symmetries, has a close relation to complete transversal of singularities theory. Applying the method developed in this thesis, the resulting normal form is a formal series which does not depend of the computation of the kernel of the so called homologic operator. Normal forms of two classes of non-resonant and resonant cases are presented, for dierent representations of the group \'Z INT. 2\' x \'Z INT. 2\' - with linearization having a 2 - dimensional nilpotent part and a semisimple part with purely imaginary eigenvalues

110f. / Submitted by Suelen Reis (suziy.ellen@gmail.com) on 2013-04-29T14:49:12Z No. of bitstreams: 1 Dissertacao_Carla Mendes.pdf: 654590 bytes, checksum: 456846ec0dc1d16e2c11b727af6c9886 (MD5) / Approved for entry into archive by Maria Auxiliadora Lopes(silopes@ufba.br) on 2013-05-03T19:16:21Z (GMT) No. of bitstreams: 1 Dissertacao_Carla Mendes.pdf: 654590 bytes, checksum: 456846ec0dc1d16e2c11b727af6c9886 (MD5) / Made available in DSpace on 2013-05-03T19:16:21Z (GMT). No. of bitstreams: 1 Dissertacao_Carla Mendes.pdf: 654590 bytes, checksum: 456846ec0dc1d16e2c11b727af6c9886 (MD5) Previous issue date: 2002 / Trata-se de uma pesquisa propositiva teórico-prática para o tratamento dos temas transversais no ensino médio, com ênfase nas dimensões estética e ética, pela realização de oficinas teatrais e posterior montagem e apresentação de uma mostra cênica com os participantes. São sugeridos caminhos de ações educativas que permitam ao educando ressignificar o objeto de conhecimento de maneira criativa, reflexiva e prazerosa, levando-se em consideração as singularidades da adolescência, o espírito do tempo e as complexidades do mundo contemporâneo. Finalmente, esta proposta possui como princípio fundante, a perspectiva e a possibilidade concreta de uma Educação com a Vida, assim como, a necessidade premente de que professores e alunos estabeleçam uma parceria afetiva e efetiva, de desenvolvimento pessoal e coletivo, a fim de que transformações construtivas aconteçam na escola e no mundo. / Salvador

In this thesis we consider extensions and generalizations of some classical problems in Combinatorial Geometry. Our work is an offshoot of four classical problems in Combinatorial Geometry. A fundamental assumption in these problems is that the underlying point set is R2. Two fundamental themes entwining the problems considered in this thesis are: “What happens if we assume that the underlying point set is finite?”, “What happens if we assume that the underlying point set has a special structure?”. Let P ⊂ R2 be a finite set of points in general position. It is reasonable to expect that if |P| is large then certain ‘patterns’ in P always occur. One of the first results was the Erd˝os-Szekeres Theorem which showed that there exists a f(n) such that if |P| ≥ f(n) then there exists a convex subset S ⊆ P, |S| = n i.e., a subset which is a convex polygon of size n. A considerable number of such results have been found since. Avis et al. in 2001 posed the following question which we call the n-interior point problem: Is there a finite integer g(n) for every n, such that, every point set P with g(n) interior points has a convex subset S ⊆ P with n interior points. i.e. a subset which is a convex polygon that contains exactly n interior points. They showed that g(1) = 1, g(2) = 4. While it is known that g(3) = 9, it is not known whether g(n) exists for n ≥ 4. In the first part of this thesis, we give a positive solution to the n-interior point problem for point sets with bounded number of convex layers. We say a family of geometric objects C in Rd has the (l, k)-property if every subfamily C′ ⊆ C of cardinality at most l is k-piercable. Danzer and Gr¨unbaum posed the following fundamental question which can be considered as a generalised version of Helly’s theorem: For every positive integer k, does there exist a finite g(k, d) such that if any family of convex objects C in Rd has the (g(k, d), k)-property, then C is k-piercable? Very few results(mostly negative) are known. Inspired by the original question of Danzer and Gr¨unbaum we consider their question in an abstract set theoretic setting. Let U be a set (possibly infinite). Let C be a family of subsets of U with the property that if C1, . . . ,Cp+1 ∈ C are p + 1 distinct subsets, then |C1 ∩ · · · ∩Cp+1| ≤ l. In the second part of this thesis, we show in this setting, the first general positive results for the Danzer Grunbaum problem. As an extension, we show polynomial sized kernels for hitting set and covering problems in our setting. In the third part of this thesis, we broadly look at hitting and covering questions with respect to points and families of geometric objects in Rd. Let P be a subset of points(possibly infinite) in Rd and C be a collection of subsets of P induced by objects of a given family. For the system (P, C), let νh be the packing number and νc the dual packing number. We consider the problem of bounding the transversal number τ h and the dual transversal number τ c in terms of νh and νc respectively. These problems has been well studied in the case when P = R2. We systematically look at the case when P is finite, showing bounds for intervals, halfspaces, orthants, unit squares, skylines, rectangles, halfspaces in R3 and pseudo disks. We show bounds for rectangles when P = R2. Given a point set P ⊆ Rd, a family of objects C and a real number 0 < ǫ < 1, the strong epsilon net problem is to find a minimum sized subset Q ⊆ P such that any object C ∈ C with the property that |P ∩C| ≥ ǫn is hit by Q. It is customary to express the bound on the size of the set Q in terms of ǫ. Let G be a uniform √n × √n grid. It is an intriguing question as to whether we get significantly better bounds for ǫ-nets if we restrict the underlying point set to be the grid G. In the last part of this thesis we consider the strong epsilon net problem for families of geometric objects like lines and generalized parallelograms, when the underlying point set is the grid G. We also introduce the problem of finding ǫ-nets for arithmetic progressions and give some preliminary bounds.

This PhD thesis is comprised of 3 results in computational geometry and graph theory. In the first paper, I demonstrate that the piercing number of a set S of pairwise intersecting convex shapes in the plane is bounded by O(\alpha(S)), where \alpha(S) is the fatness of the set S, improving upon the previous upper-bound of O(\alpha(S)^2). In the second article, I show that anagram-free vertex colouring of a 2\times n square grid requires a number of colours that increases with n. This answers an open question in Wilson's thesis and shows that even graphs of pathwidth 2 do not have anagram-free colouring with a bounded number of colours. The third article is a study on the geodesic anagram-free chromatic number of chordal and interval graphs. \emph{Geodesic anagram-free chromatic number} is defined as the minimum number of colours required to colour a graph such that all shortest paths between any pair of vertices are coloured anagram-free. In particular, I prove that the geodesic anagram-free chromatic number of a chordal graph G is 32p'w, where p' is the pathwidth of the subtree intersection representation graph (tree) of G, and w is the clique number of G. Additionally, I prove that the geodesic anagram-free chromatic number of an interval graph is bounded by 32p, where p is the pathwidth of the interval graph. This PhD thesis is comprised of 3 results in computational geometry and graph theory.

Dans cette thèse, nous nous intéressons à la résolution exacte de problèmes NP-difficiles sur les graphes et les hypergraphes. Les problèmes que nous étudions regroupent dans un premier temps des variantes du problème classique du nombre chromatique. Les variantes de ce problème se distinguent par la difficulté introduite par les relations entre les classes de couleurs, ou la difficulté de reconnaissance des classes de couleurs elles-mêmes. Puis nous ferons le lien avec les problèmes de transversaux sur les hypergraphes. Plus particulièrement, il s’agira de s’intéresser à l’énumération de transversaux minimaux dans un hypergraphe de rang borné. Outre la résolution exacte, nous nous intéressons à la résolution à paramètre fixe. Le problème de racine carrée de graphe est un problème important en théorie des graphes. Nous proposons et montrons la solubilité à paramètre fixe de deux problèmes d’optimisation reliés. Finalement, nous nous intéresserons à la résolution de problèmes de graphe, soit en lien avec les problèmes de colorations, soit pour montrer les performances possibles de différents algorithmes en fonction de l’espace mémoire disponible. Dans cette thèse, nous aurons à cœur d’appliquer judicieusement la grande majorité des techniques essentielles en algorithmique exacte exponentielle. Principalement, nous appliquerons la programmation dynamique ou le principe d’inclusion-exclusion pour les problèmes de coloration. La technique de programmation dynamique se retrouvera pour d’autres problèmes de cette thèse, aux côtés d’autres méthodes comme la technique de branchement ou de mesurer et conquérir / In this thesis, we are interested in the exact computation of np-hard problems on graphs and hypergraphs. Firstly, we study several variants of colorings. Those variants appear harder than the famous chromatic number problem, by adding difficulty in recognizing the color classes, or more often by introducing various relationships between them. Then we link to problems of transversals in hypergraphs. More precisely, we are interested in enumerating minimal transversals in bounded ranked hypergraphs. Besides the exact computation, we are also interested in fixed parameter tractability. For this area, we study two optimization versions of the famous square root of graphs problem. Finally, we will be interested in solving other problems of graphs related to colorings, or in order to compare efficiencies of algorithms depending on the memory space available. In this thesis, we will apply most of major techniques in designing exact exponential algorithms. The main techniques we use are dynamic programming, inclusion-exclusion, branching, or measure and conquer

El treball Estudi de sals foses mitjançant la dinàmica molecular està integrat dins la línia de recerca Simulació de comportament atòmic en la matèria condensada i amb ell s'han assolit dos grans objectius. El primer consisteix en completar l'estudi de les sals foses binàries d'ions monovalents (sals 1:1), que ja s'havia iniciat en aquest grup de recerca, amb l'estudi del AgCl, AgBr i dels halurs de tal·li (TlCl, TlBr i TlI). El segon és ampliar l'estudi de la dinàmica col·lectiva dels halurs de coure fosos amb l'estudi de les fluctuacions locals de les densitats parcials de partícules, de massa i de càrrega, i dels seus corrents longitudinals i transversals. Els resultats corresponents els presentem per separat en la part I i II de la memòria.Comencem la primera part amb el capítol 1, fent una introducció a les sals 1:1 foses que havien estat estudiades anteriorment, és a dir, els halurs alcalins i els halurs de coure i el AgI. Posem de relleu les característiques principals d'aquestes sals i expliquem els models que s'han utilitzat per estudiar-les.En el segon capítol proposem un mètode per determinar els factors d'estructura estàtics, que permet optimitzar el temps de càlcul i alhora obtenir unes funcions sense gaire soroll. El fet de disposar de bons factors d'estructura estàtics permet la comparació amb resultats experimentals de difracció elàstica de neutrons. A més a més, en aquest capítol aprofitem per descriure a l'espai recíproc les propietats estructurals dels halurs alcalins i de coure fosos. En els capítols tercer i quart, presentem els resultats de la dinàmica molecular del AgCl i el AgBr, i dels halurs de tal·li, respectivament. Aquestes sals s'han modelat considerant els potencials proposats conjuntament amb els Drs. Moises Silbert i Çetin Tasseven de la Universitat de East Anglia. Aquests potencials permeten reproduir bastant bé els factors d'estructura i les conductivitats iòniques experimentals. L'anàlisi de les funcions de distribució radial i els factors d'estructura estàtics, així com de les funcions de correlació de velocitats i els desplaçaments quadràtics mitjans, mostra que aquestes sals tenen un comportament intermedi entre els halurs alcalins (on els anions i cations tenen una mida molt semblant) i els halurs de coure (on els cations són molt més petits que els anions). També hem fet un estudi de la influència de la massa i la mida dels ions en la seva dinàmica individual.A la Part II del treball, per tal d'estudiar les fluctuacions de densitat i dels corrents en els halurs de coure fosos hem triat el CuCl i el CuI. En el CuCl els ions més grans (els anions) són més lleugers que els cations, en canvi, en el CuI són més pesants. A més a més, aquest estudi l'hem completat amb dos halurs alcalins com el KCl i el RbCl. En aquestes dues sals els cations i els anions són de mida semblant, però mentre que en el RbCl els anions són més lleugers que els cations, en el KCl tenen quasi la mateixa massa. D'aquesta manera podem veure quina és la influència de la massa i la mida en aquestes propietats.En el capítol cinc estudiem el procés d'autodifusió dels ions mitjançant les funcions de scattering intermèdies self i els seus espectres, anomenats factors d'estructura dinàmics self. A l'últim apartat comparem els resultats de les nostres simulacions per al CuCl amb els resultats experimentals de difracció quasielàstica de neutrons obtinguts pel Dr. Spencer Howells del Rutherford Appleton Laboratory.El capítol sis l'hem dedicat a les fluctuacions de densitat en sals 1:1 foses mitjançant les funcions de scattering intermèdies i els corresponents factors d'estructura dinàmics. Aquestes funcions revelen la presència de modes col·lectius acústics i òptics associats a les fluctuacions de la densitat de massa i de càrrega, respectivament. Aquests modes són una reminiscència dels modes acústic i òptic a l'estat sòlid.En el capítol set estudiem de les correlacions entre els corrents longitudinals i transversals, així com dels modes col·lectius que hi estan relacionats.Finalment presentem les conclusions i les perspectives de continuació d'aquest treball. A més a més, hem inclòs cinc apèndix on fem un recull argumentat de totes les definicions de les propietats que hem calculat.