Geometric covering is a well-studied topic in computational geometry. We study three covering problems: Disjoint Unit-Disk Cover, Depth-(≤ K) Packing and Red-Blue Unit-Square Cover. In the Disjoint Unit-Disk Cover problem, we are given a point set and want to cover the maximum number of points using disjoint unit disks. We prove that the problem is NP-complete and give a polynomial-time approximation scheme (PTAS) for it. In Depth-(≤ K) Packing for Arbitrary-Size Disks/Squares, we are given a set of arbitrary-size disks/squares, and want to find a subset with depth at most K and maximizing the total area. We prove a depth reduction theorem and present a PTAS. In Red-Blue Unit-Square Cover, we are given a red point set, a blue point set and a set of unit squares, and want to find a subset of unit squares to cover all the blue points and the minimum number of red points. We prove that the problem is NP-hard, and give a PTAS for it. A "mod-one" trick we introduce can be applied to several other covering problems on unit squares.

The maximum subarray problem is to find the array portion that maximizes the sum of array elements in it. This problem was first introduced by Grenander and brought to computer science by Bentley in 1984. This problem has been branched out into other problems based on their characteristics. k-overlapping maximum subarray problem where the overlapping solutions are allowed, and k-disjoint maximum subarray problem where all the solutions are disjoint from each other are those. For k-overlapping maximum subarray problems, significant improvement have been made since the problem was first introduced. For k-disjoint maximum subarrsy, Ruzzo and Tompa gave an O(n) time solution for one-dimension. This solution is, however, difficult to extend to two-dimensions. While a trivial solution of O(kn^3) time is easily obtainable for two-dimensions, little study has been undertaken to better this. This paper introduces a faster algorithm for the k-disjoint maximum sub-array problem under the conventional RAM model, based on distance matrix multiplication. Also, DMM reuse technique is introduced for the maximum subarray problem based on recursion for space optimization.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-23T15:16:49Z No. of bitstreams: 1 JOSÉ EDER SALVADOR DE VASCONCELOS - DISSERTAÇÃO PPGMAT 2009..pdf: 634118 bytes, checksum: e65e70c702364b197a36f09e8d1ef296 (MD5) / Made available in DSpace on 2018-07-23T15:16:49Z (GMT). No. of bitstreams: 1 JOSÉ EDER SALVADOR DE VASCONCELOS - DISSERTAÇÃO PPGMAT 2009..pdf: 634118 bytes, checksum: e65e70c702364b197a36f09e8d1ef296 (MD5) Previous issue date: 2009-11 / Capes / O número de cocircuitos disjuntos em uma matróide é delimitado pelo seu posto. Existem, no entanto, matróides de posto arbitrariamente grande que não contêm dois cocircuitos disjuntos. Considere, por exemplo,M(Kn) eUn,2n. Além disso, a matróide bicircularB(Kn) pode ter posto arbitrariamente grande, mas não tem 3 cocircuitos disjuntos. Nós apresentaremos uma prova, obtida por Jim Geelen e Kasper Kabell em (5), para o seguinte fato: para cadak en, existe uma constantec tal que, seM é uma matróide com posto no mínimoc, entãoM temk cocircuitos disjuntos ou contém uma das seguintes matróides como menorUn,2n,M(Kn) ouB(Kn). / The number of disjoint cocircuits in a matroid is bounded by its rank. There are, however, matroids of rank arbitrarily large that do not contain two disjoint cocircuits. Consider, for example,M(kn) andUn,2n. Moreover, the bicircular matroidB(kn) may have arbitrarily large rank but do not have 3 disjoints cocircuits. We show a proof obtained by Jim Geelen and Kasper Kabell in (5) to the following fact: for everyk andn, there is a constantc such that ifM is a matroid with rank at leastc, thenM hask disjoint cocircuits orM contains one of the following matroids as a minorUn,2n, M(kn) orB(kn).

The article gives a constructions of k-tuples of topological spaces such that the product of the k-tuple is not Frchet-Urysohn but all smaller subproducts are. The construction uses almost disjoint systems. The article repeats the construction by Petr Simon of two such compact spaces. To achieve more dimensional example there are generalized terms of AD systems. The example is constructed under the assumption of existence of a strong completely separable MAD system. It is then constructed under the assumption s ≤ b where s is the splitting number and b is the bounding number.

Given a simple graph G with vertex set V(G)={1,2,...,n} define S(G) to be the set of all real symmetric matrices A such that for all i not equal to j, the ijth entry of A is nonzero if and only if ij is in E(G). The range of the ranks of matrices in S(G) is of interest and can be determined by finding the minimum rank. The minimum rank of a graph, denoted mr(G), is the minimum rank achieved by a matrix in S(G). The maximum nullity of a graph, denoted M(G), is the maximum nullity achieved by a matrix in S(G). Note that mr(G)+M(G)=|V(G)| and so in finding the maximum nullity of a graph, the minimum rank of a graph is also determined. The minimum rank problem for a graph G asks us to determine mr(G) which in general is very difficult. A simple graph is planar if there exists a drawing of G in the plane such that any two line segments representing edges of G intersect only at a point which represents a vertex of G. A planar drawing partitions the rest of the plane into open regions called faces. A graph is outerplanar if there exists a planar drawing of G such that every vertex lies on the outer face. We consider the class of outerplanar graphs and summarize some of the recent results concerning the minimum rank problem for this class. The path cover number of a graph, denoted P(G), is the minimum number of vertex-disjoint paths needed to cover all the vertices of G. We show that for all outerplanar graphs G, P(G)is greater than or equal to M(G). We identify a subclass of outerplanar graphs, called partial 2-paths, for which P(G)=M(G). We give a different characterization for another subset of outerplanar graphs, unicyclic graphs, which determines whether M(G)=P(G) or M(G)=P(G)-1. We give an example of a 2-connected outerplanar graph for which P(G) ≥ M(G).A cover of a graph G is a collection of subgraphs of G such that the union of the edge sets of the subgraphs is equal to the E(G). The rank-sum of a cover C of G is denoted as rs(C) and is equal to the sum of the minimum ranks of the subgraphs in C. We show that for an outerplanar graph G, there exists an edge-disjoint cover of G consisting of cliques, stars, cycles, and double cycles such that the rank-sum of the cover is equal to the minimum rank of G. Using the fact that such a cover exists allows us to show that the minimum rank of a weighted outerplanar graph is equal to the minimum rank of its underlying simple graph.

Neste trabalho consideramos um problema da Antropologia. A modelagem de sociedades e casamentos de indivíduos é feita com grafos mistos e encontrar caminhos disjuntos é uma questão central no problema. O problema é NP-completo e, quando visto como um problema parametrizado, ele é W[1]-difícil. Alguns subproblemas que surgem durante o processo de obter uma solução para o problema, envolvem caminhos disjuntos e podem ser resolvidos em tempo polinomial. Implementamos algoritmos polinomiais que são usados em uma ferramenta desenvolvida para solucionar o problema na Antropologia considerado. Nossa solução funcionou bem para as sociedades fornecidas pelos nossos parceiros. / In this work we consider a problem from the Anthropology. The model of the societies and the marriages of individuals is done with mixed graphs and to find disjoint paths is a central question in the problem. The problem is NP-complete and W[1]-hard when it is considered a parameterized problem. Some subproblems that arise during the process to obtain a solution for the problem, involve disjoint paths and can be solved in polynomial time. We implemented some polynomial algorithms that are used in a tool developed to solve the problem in the Anthropology considered. Our solution worked well for the societies provided by our partners.

Die Theorie disjunkter NP-Paare, die auf natürliche Weise statt einzelner Sprachen Paare von NP-Mengen zum Objekt ihres Studiums macht, ist vor allem wegen ihrer Anwendungen in der Kryptografie und Beweistheorie interessant. Im Zentrum dieser Dissertation steht die Analyse der Beziehung zwischen disjunkten NP-Paaren und aussagenlogischen Beweissystemen. Haben die Anwendungen der NP-Paare in der Beweistheorie maßgeblich das Verständnis aussagenlogischer Beweissysteme gefördert, so beschreiten wir in dieser Arbeit gewissermaßen den umgekehrten Weg, indem wir Methoden der Beweistheorie zur genaueren Untersuchung des Verbands disjunkter NP-Paare heranziehen. Insbesondere ordnen wir jedem Beweissystem P eine Klasse DNPP(P) von NP-Paaren zu, deren Disjunktheit in dem Beweissystem P mit polynomiell langen Beweisen gezeigt werden kann. Zu diesen Klassen DNPP(P) zeigen wir eine Reihe von Resultaten, die illustrieren, dass robust definierten Beweissystemen sinnvolle Komplexitätsklassen DNPP(P) entsprechen. Als wichtiges Hilfsmittel zur Untersuchung aussagenlogischer Beweissysteme und der daraus abgeleiteten Klassen von NP-Paaren benutzen wir die Korrespondenz starker Beweissysteme zu erststufigen arithmetischen Theorien, die gemeinhin unter dem Schlagwort beschränkte Arithmetik zusammengefasst werden. In der Praxis trifft man statt auf zwei häufig auf eine größere Zahl konkurrierender Bedingungen. Daher widmen wir uns der Erweiterung der Theorie disjunkter NP-Paare auf disjunkte Tupel von NP-Mengen. Unser Hauptergebnis in diesem Bereich besteht in der Charakterisierung der Fragen nach der Existenz optimaler Beweissysteme und vollständiger NP-Paare mit Hilfe disjunkter Tupel. / Disjoint NP-pairs are an interesting complexity theoretic concept with important applications in cryptography and propositional proof complexity. In this dissertation we explore the connection between disjoint NP-pairs and propositional proof complexity. This connection is fruitful for both fields. Various disjoint NP-pairs have been associated with propositional proof systems which characterize important properties of these systems, yielding applications to areas such as automated theorem proving. Further, conditional and unconditional lower bounds for the separation of disjoint NP-pairs can be translated to results on lower bounds to the length of propositional proofs. In this way disjoint NP-pairs have substantially contributed to the understanding of propositional proof systems. Conversely, this dissertation aims to transfer proof-theoretic knowledge to the theory of NP-pairs to gain a more detailed understanding of the structure of the class of disjoint NP-pairs and in particular of the NP-pairs defined from propositional proof systems. For a proof system P we introduce the complexity class DNPP(P) of all disjoint NP-pairs for which the disjointness of the pair is efficiently provable in the proof system P. We exhibit structural properties of proof systems which make the previously defined canonical NP-pairs of these proof systems hard or complete for DNPP(P). Moreover, we demonstrate that non-equivalent proof systems can have equivalent canonical pairs and that depending on the properties of the proof systems different scenarios for DNPP(P) and the reductions between the canonical pairs exist. As an important tool for our investigation we use the connection of propositional proof systems and disjoint NP-pairs to theories of bounded arithmetic.

In its theoretical part, this thesis sums up the basic knowledge concerning permutations. Besides the representation of permutations and determination of their fundamental characteristics, the theoretical part is, first of all, aimed at results concerning the decomposition of permutations into disjoint cycles and at finding the number of permutations with a certain characteristic. We introduce the fundamental bijection that is useful for solving many problems concerning the permutations. Further on, we focus on the number of permutations without a fixed point, Eulerian numbers expressing the number of permutations with a given number of descents, and the number of permutations with a given number of excedances, Stirling numbers of the first kind expressing the number of permutations with a given number of cycles, and Catalan numbers representing the number of permutations avoiding a chosen pattern of length three. Attention is also paid to the Gilbreath permutations and their characteristics. The practical part consists of 14 solved problems. The solutions rely on the results presented in the theoretical part, and there are deduced some further interesting results concerning random permutations.

La sécurisation inhérente aux échanges dans les environnements dynamiques et distribués, dépourvus d’une coordination centrale et dont la topologie change perpétuellement, est un défi majeur. Dans le cadre de cette thèse, on se propose en effet de définir une infrastructure de sécurité adaptée aux contraintes des systèmes P2P actuels. Le premier volet de nos travaux consiste à proposer un intergiciel, appelé SEMOS, qui gère des sessions sécurisées et mobiles. SEMOS permet en effet de maintenir les sessions sécurisées actives et ce, même lorsque la configuration réseau change ou un dysfonctionnement se produit. Cette faculté d’itinérance est rendue possible par la définition d’un nouveau mécanisme de découplage afin de cloisonner l’espace d’adressage de l’espace de nommage ; le nouvel espace de nommage repose alors sur les tables de hachage distribuées (DHT). Le deuxième volet définit un mécanisme distribué et générique d’échange de clés adapté à l’architecture P2P. Basé sur les chemins disjoints et l’échange de bout en bout, le procédé de gestion des clés proposé est constitué d’une combinaison du protocole Diffie-Hellman et du schéma à seuil(k, n) de Shamir. D’une part, l’utilisation des chemins disjoints dans le routage des sous-clés compense l’absence de l’authentification certifiée, par une tierce partie, consubstantielle au protocole Diffie-Hellman et réduit, dans la foulée, sa vulnérabilité aux attaques par interception. D’autre part, l’extension de l’algorithme Diffie-Hellman par ajout du schéma à seuil (k, n) renforce substantiellement sa robustesse notamment dans la segmentation des clés et/ou en cas de défaillances accidentelles ou délibérées dans le routage des sous-clés. Enfin, les sessions sécurisées mobiles sont évaluées dans un réseau virtuel et mobile et la gestion des clés est simulée dans un environnement générant des topologies P2P aléatoires. / Securing communications in distributed dynamic environments, that lack a central coordination point and whose topology changes constantly, is a major challenge.We tackle this challenge of today’s P2P systems. In this thesis, we propose to define a security infrastructure that is suitable to the constraints and issues of P2P systems. The first part of this document presents the design of SEMOS, our middleware solution for managing and securing mobile sessions. SEMOS ensures that communication sessions are secure and remain active despite the possible disconnections that can occur when network configurations change or a malfunction arises. This roaming capability is implemented via the definition of a new addressing space in order to split up addresses for network entities with their names ; the new naming space is then based on distributed hash tables(DHT). The second part of the document presents a generic and distributed mechanism for a key exchange method befitting to P2P architectures. Building on disjoint paths andend-to-end exchange, the proposed key management protocol consists of a combination of the Diffie-Hellman algorithm and the Shamir’s (k, n) threshold scheme. On the onehand, the use of disjoint paths to route subkeys offsets the absence of the third party’s certified consubstantial to Diffie-Hellman and reduces, at the same time, its vulnerability to interception attacks. On the other hand, the extension of the Diffie-Hellman algorithm by adding the threshold (k, n) scheme substantially increases its robustness, in particular in key splitting and / or in the case of accidental or intentional subkeys routing failures. Finally, we rely on a virtual mobile network to assess the setup of secure mobile sessions.The key management mechanism is then evaluated in an environment with randomly generated P2P topologies.

Contrôleurs utilisés dans les systèmes autotestables pour le test des sorties combinatoires ou séquentielles. Conception des contrôleurs NMOS à partir de l'assemblage des cellules, des règles de conception pour celle-ci, et des hypothèses de pannes pouvant survenir. Les considérations pratiques sont basées sur des hypothèses de pannes analytiques