Avoiding the negative effects of habitat fragmentation on biodiversity is especially challenging when also the management institutions are spatially and administratively distributed. This doctoral thesis introduces five case studies that investigate ecological, social and social-ecological relations in fragmented landscapes. I present new approaches in which research and governance can detect and manage mismatches between landscape ecology and planning. The case studies include urban and forested landscapes where an intense land-use is limiting the connectivity, i.e., the potential for many species to disperse between the remaining patches of habitat. Graph-theoretic (network) models are applied to map connectivity patterns and to estimate the outcome for dispersing species at the patch level and for the whole study system. In particular, the network models are applied to evaluate the spatial complexity and the potential mismatches between ecological connectivity and geographically distributed management institutions like protected areas and municipalities. Interviews with municipal ecologists complement the spatial analysis; revealing some problems and ways forward regarding the communication and integration of ecological knowledge within local spatial-planning agencies. The results also show that network models are useful to identify and communicate critical ecological and social-ecological patterns that call for management attention. I suggest some developments of network models as to include interactions between species and across governance levels. Finally, I conclude that more effort is needed for network models to materialize into ecological learning and transformation in management processes. / <p>At the time of the doctoral defence the following papers were unpublished and had a status as follows: Paper 1: Manuscript. Paper 2: Manuscript.</p>

This document is a long abstract of my research work, concerning graph theory and algorithms on graphs. It summarizes some results, gives ideas of the proof for some of them and presents the context of the different topics together with some interesting open questions connected to them The first part precises the notations used in the rest of the paper; the second part deals with some problems on cycles in digraphs; the third part is an overview of two graph coloring problems and one problem on structures in colored graphs; finally the fourth part focus on some results in algorithmic graph theory, mainly in parametrized complexity.

In graph theory graphs are mathematical objects that can be used to model networks, data structures, process scheduling, computations and a variety of other systems where the relations between the objects in the system play a dominant role.We will now consider graphs as mathematically self-contained units with rich structure and comprehensive theory; as models for many phenomena, particularly those arising in computer systems; and as structures which can be processed by a variety of sophisticated and interesting algorithms.For graph theory presentation, we need a very good graphical user interface(GUI) to approach the goal. X Window system is ideally suited for such a purpose. This package program is based on X Window system environment. With this package, we can manipulate graphs by special functions which can put nodes, put edges, delete nodes, delete edges, change the whole graph size, move graph location, and modify edge weights. / Department of Computer Science

In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.

We define a variation of injective oriented colouring as reflexive injective oriented colouring, or rio-colouring for short, which requires an oriented colouring to be injective on the neighbourhoods of the underlying graph, without requiring the colouring to be proper. An analysis of the complexity of the problem of deciding whether an oriented graph has a k-rio-colouring is considered, and we find a dichotomy for the values of k below 3 and above, being in P or NP-complete, respectively. Characterizations are given for the oriented graphs resulting from the polynomial-time solvable cases, and bounds are given for the rio-chromatic number in terms of maximum in-degree and out-degree, in general, and for oriented trees. Also, a polynomial-time algorithm is developed to aid in the rio-colouring of oriented trees.

Many graphs arising in practice can be represented in a concise and intuitive way that conveys their structure. For example: A planar graph can be represented in the plane with points for vertices and non-crossing curves for edges. An interval graph can be represented on the real line with intervals for vertices and intersection of intervals representing edges. The concept of ``simultaneity'' applies for several types of graphs: the idea is to find representations for two graphs that share some common vertices and edges, and ensure that the common vertices and edges are represented the same way. Simultaneous representation problems arise in any situation where two related graphs should be represented consistently. A main instance is for temporal relationships, where an old graph and a new graph share some common parts. Pairs of related graphs arise in many other situations. For example, two social networks that share some members; two schedules that share some events, overlap graphs of DNA fragments of two similar organisms, circuit graphs of two adjacent layers on a computer chip etc. In this thesis, we study the simultaneous representation problem for several graph classes. For planar graphs the problem is defined as follows. Let G1 and G2 be two graphs sharing some vertices and edges. The simultaneous planar embedding problem asks whether there exist planar embeddings (or drawings) for G1 and G2 such that every vertex shared by the two graphs is mapped to the same point and every shared edge is mapped to the same curve in both embeddings. Over the last few years there has been a lot of work on simultaneous planar embeddings, which have been called `simultaneous embeddings with fixed edges'. A major open question is whether simultaneous planarity for two graphs can be tested in polynomial time. We give a linear-time algorithm for testing the simultaneous planarity of any two graphs that share a 2-connected subgraph. Our algorithm also extends to the case of k planar graphs, where each vertex [edge] is either common to all graphs or belongs to exactly one of them. Next we introduce a new notion of simultaneity for intersection graph classes (interval graphs, chordal graphs etc.) and for comparability graphs. For interval graphs, the problem is defined as follows. Let G1 and G2 be two interval graphs sharing some vertices I and the edges induced by I. G1 and G2 are said to be `simultaneous interval graphs' if there exist interval representations of G1 and G2 such that any vertex of I is assigned to the same interval in both the representations. The `simultaneous representation problem' for interval graphs asks whether G1 and G2 are simultaneous interval graphs. The problem is defined in a similar way for other intersection graph classes. For comparability graphs and any intersection graph class, we show that the simultaneous representation problem for the graph class is equivalent to a graph augmentation problem: given graphs G1 and G2, sharing vertices I and the corresponding induced edges, do there exist edges E' between G1-I and G2-I such that the graph G1 U G_2 U E' belongs to the graph class. This equivalence implies that the simultaneous representation problem is closely related to other well-studied classes in the literature, namely, sandwich graphs and probe graphs. We give efficient algorithms for solving the simultaneous representation problem for interval graphs, chordal graphs, comparability graphs and permutation graphs. Further, our algorithms for comparability and permutation graphs solve a more general version of the problem when there are multiple graphs, any two of which share the same common graph. This version of the problem also generalizes probe graphs.

Many countries are reporting of difficulties in exact education at schools: mathematics, informatics, physics etc. Various methods are proposed to awaken and preserve students’ interest in these disciplines. Among them, the simplification, accent on applications, avoiding of argumentation (especially in mathematics) etc. must be mentioned. As one of reasons for these approaches the growing amount of knowledge/skills to be acquired at school is often mentioned. In this paper we consider one of the possibilities to integrate partially teaching of important chapters of discrete mathematics and informatics not reducing the high educational standards. The approach is based on the identification and mastering general combinatorial principles underlying many topics in both disciplines. A special attention in the paper is given to the so-called “pigeonhole principle” and its generalizations. In folklore, this principle is usually formulated in the following way: “if there are n + 1 rabbits in n cages, you can find a cage with at least two rabbits in it“. Examples of appearances of this principle both in mathematics and in computer science are considered.

Graphs are a fundamental and widely-used abstraction for representing data. We can analytically study interesting aspects of real-world complex systems such as the Internet, social systems, transportation networks, and biological interaction data by modeling them as graphs. Graph-theoretic and combinatorial problems are also pervasive in scientific computing and engineering applications. In this dissertation, we address the problem of analyzing large-scale complex networks that represent interactions between hundreds of thousands to billions of entities. We present SNAP, a new high-performance computational framework for efficiently processing graph-theoretic queries on massive datasets. Graph analysis is computationally very different from traditional scientific computing, and solving massive graph-theoretic problems on current high performance computing systems is challenging due to several reasons. First, real-world graphs are often characterized by a low diameter and unbalanced degree distributions, and are difficult to partition on parallel systems. Second, parallel algorithms for solving graph-theoretic problems are typically memory intensive, and the memory accesses are fine-grained and highly irregular. The primary contributions of this dissertation are the design and implementation of novel parallel graph algorithms for traversal, shortest paths, and centrality computations, optimized for the small-world network topology, and high-performance multithreaded architectures and multicore servers. SNAP (Small-world Network Analysis and Partitioning) is a modular, open-source framework for the exploratory analysis and partitioning of large-scale networks. With SNAP, we demonstrate the capability to process massive graphs with billions of vertices and edges, and achieve up to two orders of magnitude speedup over state-of-the-art network analysis approaches. We also design a new parallel computing benchmark for characterizing the performance of graph-theoretic problems on high-end systems; study data representations for dynamic graph problems on parallel systems; and apply algorithms in SNAP to solve real-world problems in social network analysis and systems biology.

Zugl.: Bern, Univ., Diss., 2005

La consommation d'énergie augmente d'année en année en raison de la croissance de la population et des conditions économiques. Afin de répondre aux besoins de la population et de la société d'utiliser l'électricité, le Gouvernement Cambodgien a mis en place la politique de promotion et d'encouragement du développement de l’électrification ; tous les villages auront de l'électricité d'ici 2020 et au moins 70% des domiciles auront accès à la bonne qualité du réseau électrique d'ici 2030. Pour réussir ces objectifs, l'étude et le développement de la méthodologie du réseau de distribution basse tension (BT) sont étudiés. Cette thèse étudie la planification du réseau de distribution BT avec intégration de Photovoltaïque (PV) et de stockage d’énergie de batterie (BES). La première partie est développée la méthode de planification à long terme pour tacler le défi de l'incertitude sur la charge en zone urbaine ;le nouvel algorithme a été développé pour rechercher l'architecture optimale de minimisation du coût d’investissement (CAPEX) et d’exploitation (OPEX) qui respecte l'ensemble de contraintes topologies et électriques (courant et tension) grâce à la programmation linéaire mixte en nombres entiers à contraintes quadratiques (PLMNECQ), le plus court chemin , first-fit bin-packing, et la méthode de Monte-Carlo. La deuxième partie est traité de l'extension de la zone de couverture de l'électricité avec deux solutions possibles, sont le renforcement du réseau et l'intégration de PV-BES pour le village rural ; l'algorithme génétique (GA) et la technique itérative ont été codés pour rechercher l’emplacement et la capacité. La dernière partie du travail est concentrée sur la planification du réseau de distribution résidentielle BT pour les zones non électrifiées aux rural et urbain grâce à l'architecture optimale et l'intégration de PV-BES sur l'horizon de planification. / The energy consumption is increasing year by year due to the growth of population and the economic conditions. In order to meet the need of population and society to use electricity, the Cambodian government has established the policy to promote and encourage the development of electrification; all the villages will have electricity by the year 2020, and at least 70% of households will have access to grid quality by the year 2030. To achieve these goals, the study and development of methodology on the Low-Voltage (LV) distribution system are investigated. This thesis studies the planning of LV distribution system with integration of Photovoltaic (PV) and Battery Energy Storage (BES). The first part is developed the long-term planning method to tackle the challenge of load demand uncertainty in urban area; the novel algorithm was developed to search for the optimal architecture of minimizing the capital expenditure (CAPEX) and the operation expenditure (OPEX) which respects to the set of topology and electrical (current and voltage) thank to mixed integer quadratically constrained programming (MIQCP), shortest-path, first-fit bin-packing, and Monte-Carlo method. The second part is dealt with the extension of electricity coverage area with two possible solutions which are grid reinforcement and integration of PV-BES for rural village; the Genetic algorithm (GA) and iterative technique were coded to search for location and sizing. The last part is concentrated on the planning of residential low-voltage distribution system in both rural and urban for non-electrified area thanks to the optimal architecture and PV-BES integration over the planning horizon.