The dissertation consists of two parts. In the first part several asymptotic properties of random intersection graphs are studied. They include birth thresholds for small complete subgraphs in the binomial random intersection graph, the clique number in sparse random intersection graphs and the chromatic index of random uniform hypergraphs. Several new methods and theoretically and practically relevant algorithms are proposed. Some results are illustrated with data from real-world networks. The second part deals with asymptotic enumeration and properties of graphs from minor-closed classes in the case when the excluded minors are disjoint. The class of graphs without k+1 (vertex-)disjoint cycles and more general classes of graphs without k+1 disjoint excluded minors (satisfying a condition related to fans) are considered. Typical graphs in such classes are shown to have a simple “k apex vertex” structure. Other asymptotic properties (connectivity, number of components, chromatic number, vertex degrees) are also determined. Finally, it is shown that typical graphs without k+1 disjoint minors K4 have a more complicated “2k+1 apex vertex” structure, and properties of such graphs are investigated. Part of the results is proved in greater generality. A variety of methods from computer science, graph theory, combinatorics and the theory of generating functions are applied. / Disertacijoje yra dvi pagrindinės dalys. Pirmojoje dalyje gaunami keli nauji rezultatai uždaviniams, susijusiems su atsitiktiniais sankirtų grafais. Nagrinėjamas pilnojo pografio gimimo slenkstis binominiame atsitiktiniame sankirtų grafe, didžiausios klikos eilė atsitiktiniame retame sankirtų grafe ir chromatinio indekso eilė atsitiktiniame reguliariajame hipergrafe. Sprendimams pasiūloma keletas naujų metodų, taip pat pateikiami teoriškai ir praktiškai svarbūs algoritmai. Kai kurie rezultatai iliustruojami duomenimis iš realių tinklų. Antrojoje dalyje pristatomi rezultatai grafų su uždraustaisiais minorais tematikoje, nagrinėjamas atvejis kai uždraustieji minorai yra nejungūs. Čia tiriamas asimptotinis grafų, neturinčių k+1 nepriklausomų ciklų, skaičius, rezultatai apibendrinami grafų, neturinčių k+1 uždraustųjų minorų, tačiau tenkinančių tam tikrą „vėduoklės“ apribojimą, klasėms. Įrodoma, kad tipiniai tokių klasių grafai turi paprastą „k dydžio blokatoriaus“ struktūrą, nustatomos kitos tokių grafų asimptotinės savybės (jungumas, komponenčių skaičius, viršūnių laipsniai). Galiausiai parodoma, kad tipiniai grafai, neturintys k+1 nepriklausomų minorų K4 turi sudėtingesnę „2k+1 dydžio blokatoriaus“ struktūrą ir ištiriamos kitos jų savybės. Dalis šių rezultatų įrodoma daug bendresniu atveju. Darbe pasitelkiami įvairūs informatikos, kombinatorikos, grafų, tikimybių ir generuojančiųjų funkcijų teorijos metodai.

Submitted by ANA KARLA PEREIRA RODRIGUES (anakarla_@hotmail.com) on 2017-08-22T13:57:08Z No. of bitstreams: 1 arquivototal.pdf: 1762696 bytes, checksum: 53bf47b7590ebc1271d2f0d81822f00c (MD5) / Made available in DSpace on 2017-08-22T13:57:08Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1762696 bytes, checksum: 53bf47b7590ebc1271d2f0d81822f00c (MD5) Previous issue date: 2017-02-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work aims to determine the maximum number of pairwise disjoint lines that a non-singular surface of degree d in P3 can contain. In the case of degrees d = 1 and d = 2 we found that these values are zero and in nite, respectively. Furthermore, in the case of degree d = 3 we did show that the maximum number of pairwise disjoint lines is 6, these con gurations were studied in 1863 by the Swiss Ludwig Schl a i (1814-1895) in [15]. For the case d = 4, in 1975 the Russian Viacheslav Nikulin in [10] showed that non-singular quartic surfaces contain at most 16 pairwise disjoint lines. In our work, we have been able to show that Schur's famous quartic achieves this bound and that Fermat's quartic has at most 12 pairwise disjoint lines. We also determined lower bounds for the maximum number of pairwise disjoint lines in the case of non-singular surfaces of degree d 5. For example, the Rams's family in [11] allows us to nd one of these lower bounds. / Este trabalho objetiva determinar a quantidade máxima de retas duas a duas disjuntas que uma superfície não singular de grau d em P3 pode conter. No caso dos graus d = 1 e d = 2 verificamos que estes valores s~ao zero e in nito, respectivamente. Al em disso, no caso de grau d = 3 mostramos que o n umero m aximo de retas duas a duas disjuntas e 6, ditas con gura c~oes foram estudadas em 1863 pelo sui co Ludwig Schl a i (1814-1895) em [15]. Para o caso d = 4, em 1975 o russo Viacheslav Nikulin em [10] mostrou que as superf cies qu articas n~ao singulares cont^em no m aximo 16 retas duas a duas disjuntas. No nosso trabalho, conseguimos mostrar que a famosa qu artica de Schur atinge essa cota e que qu artica de Fermat possui no m aximo 12 retas duas a duas disjuntas. Determinamos ainda cotas inferiores para o n umero m aximo de retas duas a duas disjuntas no caso de superf cies n~ao singulares de grau d 5. Por exemplo, a fam lia de Rams em [11] nos permite achar uma dessas cotas inferiores.

Made available in DSpace on 2015-05-15T11:45:58Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 634504 bytes, checksum: ce035cc957832598c53dda96372e7cb7 (MD5) Previous issue date: 2011-02-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work, based on algebraic function fields, we give constructions of disjoint linear codes. In addition,we study the asymptotic behavior of disjoint linear codes from our constructions. / Neste trabalho, baseados em corpos de funções algébricas, forneceremos construções de códigos lineares disjuntos. Além disso, nós estudaremos comportamentos assintóticos de códigos lineares disjuntos a partir da nossa construção.

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.

No description available.

Basically, the connection of two many-sorted theories is obtained by taking their disjoint union, and then connecting the two parts through connection functions that must behave like homomorphisms on the shared signature. We determine conditions under which decidability of the validity of universal formulae in the component theories transfers to their connection. In addition, we consider variants of the basic connection scheme.

Cette thèse étudie des systèmes locaux de gestion de transfert de pétrole ayant une architecture de réseau de canalisation. Pour leur représentativité, deux systèmes localisés au Venezuela et appartenant à l'entreprise PDVSA (Pétroles du Venezuela) ont été retenus pour illustrer les méthodes proposées et les valider : le Terminal Maritime de Pétrole de Guaraguao et le Centre de Stockage de Punta de Palmas. Dans ces réseaux des connexions, appelées « alignements », sont établies en ouvrant/fermant des vannes à travers d'un système SCADA (Supervisory Control and Data Acquisition). Le choix d'un alignement doit tenir compte de critères d'optimisation. La minimisation des interférences avec d'autres alignements, liée à la notion de capacité opérative, a été identifiée comme le critère de choix le plus important. Les contributions de cette thèse reposent sur une modélisation sous forme de graphes, et sur des algorithmes appartenant au domaine de la recherche opérationnelle. Elles contribuent à fournir aux opérateurs de supervision des outils d'analyse permettant d'optimiser le choix des alignements. Des indicateurs permettant de quantifier l'impact des opérations d'alignement ou des défaillances, sur la capacité opérative du système, sont proposés. La minimisation de l'impact sur la capacité opérative, va correspondre à la minimisation des interférences avec des alignements potentiels. Un algorithme de calcul de ces indicateurs, est présenté, ainsi que des algorithmes de recherche de chemin, de détermination d'éléments critiques, et de recherche d'alignements utilisant des pompes. Ces algorithmes sont basés sur des algorithmes classiques s'adressant au problème du plus court chemin, du flot maximum et du nombre maximum de chemins disjoints. Cependant, ils utilisent des méthodes innovantes, comme l'ajout de contraintes considérant l'existence de sous-types d'alignements, le calcul dynamique des coûts des chemins à partir de son impact sur la capacité opérative, et la recherche de chemins via un point intermédiaire obligatoire. Les contributions sont potentiellement applicables dans des domaines autres que le transport de pétrole. Les algorithmes ont été mis en œuvre en utilisant le langage Python et ont été testés en utilisant les données réelles des réseaux étudiés. L'objectif à moyen terme de ces travaux est le développement d'un logiciel d'assistance à la prise de décision. / This thesis studies local crude oil transportation systems with a pipe network architecture. Two representative systems, belonging to PDVSA (Venezuelan oil company), have been studied: the Guaraguao Crude Oil Seaport and the Punta de Palmas Tanks Yard. In this systems, connections, called "alignments", are established by opening/closing valves using a SCADA(Supervisory Control and Data Acquisition) system. Alignment choice is made based on optimization criteria. Interferences minimization with other alignments, related to the notion of operative capacity, has been identified as the most important criterion. The contributions of this thesis are based on graph modelling and algorithms from operational research. The main goal is to provide analysis tools allowing alignment choice optimization. Indexes permitting the quantification of alignments or failures impact on the operative capacity of the system are proposed. Minimizing the impact on the operative capacity will correspond to minimizing interferences with potential alignments. An algorithm computing these indexes is presented, as well as complementary developments such as a path search algorithm, an algorithm for critical elements determination, and algorithm for alignments using pumps. These algorithms are based on classical algorithms for the shortest path problem, the maximum flow problem and the maximum disjoint paths problem. However, they use innovative methods such as adding constraints when considering alignment sub-types, the dynamic computation of path costs based on their impact on operative capacity, and path search considering an obligatory intermediate node. These contributions can potentially be applied in areas other than oil transportation. The algorithms had been implemented in Python and had been tested using real data from the studied systems. The middle term goal of these works is the development of assistance software for decision making.

Network lifetime is a key issue in wireless sensor networks where sensor nodes, distributed typically in remote/hostile sensing areas, are powered by finite energy batteries which are not easily replaced/recharged. Depletion of these finite energy batteries can result in a change in network topology or in the end of network life itself. Hence, prolonging the life of wireless sensor networks is important. Energy consumed in wireless sensor nodes can be for the purpose of i) sensing functions, ii) processing/computing functions, and ii) communication functions. For example, energy consumed by the transmit and receive electronics constitute the energy expended for communication functions. Our focus in this thesis is on the efficient use of energy for sensing. In particular, we are concerned with energy efficient algorithms for scheduling the sensing activity of sensor nodes. By scheduling the sensing activity we mean when to activate a sensor node for sensing (active mode) and when to keep it idle (sleep mode). The novel approach we adopt in this thesis to achieve efficient scheduling of sensing activity is an information coverage approach, rather than the widely adopted physical coverage approach. In the physical coverage approach, a point is said to be covered by a sensor node if that point lies within the physical coverage range (or the sensing radius) of that sensor, which is the maximum distance between the sensor and the point up to which the sensor can sense with acceptable accuracy. Information coverage, on the other hand, exploits cooperation among multiple sensors to accurately sense a point even if that point falls outside the physical coverage range of all the sensors. In this thesis, we address the question of how to schedule the activity of various sensor nodes in the network to enhance network lifetime using information coverage. In the first part of the thesis, we are concerned with scheduling of sensor nodes for sensing point targets using information coverage – example of a point-target being temperature or radiation level at a source or point that needs to be monitored. Defining a set of sensor nodes which collectively can sense a point-target accurately as an information cover, we propose an algorithm to obtain Disjoint Set of Information Covers (DSIC) that can sense multiple point-targets in a given sensing area. Being disjoint, the resulting information covers in the proposed algorithm allow a simple round-robin schedule of sensor activation (i.e., activate the covers sequentially). We show that the covers obtained using the proposed DSIC algorithm achieve longer network life compared to the covers obtained using an Exhaustive-Greedy-Equalized Heuristic (EGEH) proposed recently in the literature. We also present a detailed complexity comparison between the DSIC and EGEH algorithms. In the second part of the thesis, we extend the point target sensing problem in the first part to a full area sensing problem, where we are concerned with energy efficient ‘area-monitoring’ using information coverage. We refer to any set of sensors that can collectively sense all points in the entire area-to-monitor as a full area information cover. We first propose a low-complexity heuristic algorithm to obtain full area information covers. Using these covers, we then obtain the optimum schedule for activating the sensing activity of various sensors that maximizes the sensing lifetime. The optimum schedules obtained using the proposed algorithm is shown to achieve significantly longer sensing lifetimes compared to those achieved using physical coverage. Relaxing the full area coverage requirement to a partial area coverage requirement (e.g., 95% of area coverage as adequate instead of 100% area coverage) further enhances the lifetime. The algorithms proposed for the point targets and full area sensing problems in the first two parts are essentially centralized algorithms. Decentralized algorithms are preferred in large networks. Accordingly, in the last part of the thesis, we propose a low-complexity, distributed sensor scheduling algorithm for full area sensing using information coverage. This distributed algorithm is shown to result in significantly longer sensing lifetimes compared to those achieved using physical coverage.

Mobile Ad Hoc Networks (MANETs) are a class of infrastructure less network architecture which are formed by a collection of mobile nodes that communicate with each other using multi-hop wireless links. They eliminate the need for central management, hence each node must operate cooperatively to successfully maintain the network. Each node performs as a source, a sink and a router. Future applications of MANETs are expected to be based on all-IP architecture, carrying a multitude of real-time multimedia applications such as voice, video and data. It would be necessary for MANETs to have an efficient routing and quality of service (QoS) mechanism to support diverse applications. This thesis proposes a set of cooperative protocols that provide support for QoS routing. The first is the on-demand, Non-Disjoint Multiple Routes Discovery protocol (NDMRD). NDMRD allows the establishment of multiple paths with node non-disjoint between source and destination node. It returns to the source a collection of routes with the QoS parameters. The second part of the protocol is the Node State Monitoring protocol for the purpose of monitoring, acquisition, dissemination and accumulation of QoS route information. The third part of the protocol implements the QoS route selection based on a Genetic Algorithm. The GA is implemented online with predetermined initial population and weighted-sum fitness function which operates simultaneously on the node bandwidth, media access delay, end to end delay and the node connectivity index (NCI). The term node connectivity index is a numerical value designed to predict comparatively the longest time a node-pair might be connected wirelessly.

Cette thèse étudie la coloration d'arcs et de cycles dans les graphes orientés. Elle se concentre sur les sujets suivants : la coloration propre d'arcs avec des sommet-distingué dans les graphes orientés, les cycles courts dans les graphes orientés avec des sous-graphes interdits, les cycles sommet-disjoints dans dans les tournois bipartis, les cycle-facteurs dans les tournois bipartis régulier et les arcs universels dans les tournois. La thèse est basée sur cinq articles originaux publiés ou présentés dans des journaux. Les principaux résultats sont les suivants. Nous introduisons la coloration propre d'arcs avec des sommet-distingué dans les graphes orientés. Nous avons proposé une conjecture sur le nombre arc-chromatique sommet-distingué et nous avons aussi donné quelque résultats partiels. Nous avons étendu un résultat de Razborov en prouvant que la conjecture de Caccetta-Häggkvist est vraie pour certains graphes orientés avec des sous-graphes interdits. Nous avons montré que chaque tournoi biparti avec degré sortant minimum au moins qr-1 contient r cycles de sommets-disjoints de toutes longueurs possibles. Le cas spécial q=2 confirme le cas du tournoi biparti de la conjecture de Bermond-Thomassen. Nous avons montré que chaque tournoi biparti k-régulier avec k>2 que l'on notera B a deux cycles complémentaires de longueurs 6 et |V(B)-6|, à moins que B soit isomorphe à un graphe spécifique, étayant ainsi une conjecture sur des 2-cycles-facteurs dans les tournois bipartis. En outre, nous montrons que tous les tournois bipartis réguliers ont un k-cycle-facteur. Nous donnons une condition nécessaire et suffisante pour l'existence d'un arc universel dans un tournoi et nous caractérisons tous les tournois où chaque arc est universel. / In this thesis, we study arc colorings and cycles in digraphs. The following topics are considered: vertex-distinguishing proper arc colorings in digraphs, short cycles in digraphs with forbidden subgraphs , disjoint cycles in bipartite tournaments, cycle factors in regualr bipartite tournaments and universal arcs in tournaments. The main results are contained in five original articles published or submitted to an international journal. We introduce vertex-distinguishing proper arc colorings of digraphs. A conjecture on the vertex-distinguishing arc-chromatic number is given and some partial results are obtained. We extend a result of Razborov by proving that the Caccetta-Häggkvist conjecture is true for digraphs with certain induced forbidden subgraphs or with certain forbidden subgraphs. We show that every bipartite tournament with minimum outdegree at least qr-1 has r vertex disjoint cycles of any given possible lengths. The special case q=2 of the result verifies the bipartite tournament case of the Bermond-Thomassen conjecture. As a partial support of a conjecture on 2-cycle-factors in bipartite tournaments, we prove that every k-regular bipartite tournament B with k>2 has two complementary cycles of lengths 6 and |V(B)|-6, unless B is isomorphic to a special digraph. Besides, we show that every k-connected regular bipartite tournament has a k-cycle-factor. We also give a sufficient and necessary condition for the existence of a universal arc in a tournament and characterize all the tournaments in which every arc is universal.