Search results for "graphs"
showing 10 items of 126 documents
Trapping of Continuous-Time Quantum walks on Erdos-Renyi graphs
2011
We consider the coherent exciton transport, modeled by continuous-time quantum walks, on Erd\"{o}s-R\'{e}ny graphs in the presence of a random distribution of traps. The role of trap concentration and of the substrate dilution is deepened showing that, at long times and for intermediate degree of dilution, the survival probability typically decays exponentially with a (average) decay rate which depends non monotonically on the graph connectivity; when the degree of dilution is either very low or very high, stationary states, not affected by traps, get more likely giving rise to a survival probability decaying to a finite value. Both these features constitute a qualitative difference with re…
Unisexual flowers as a robust synapomorphy in Cariceae (Cyperaceae)? Evidence for bisexual flowers in Schoenoxiphium
2012
Abstract Cariceae, the largest tribe within Cyperaceae, comprises about 2000 species in five genera. Cariceae is usually considered to be distinct from other Cyperaceae by the presence of exclusively unisexual flowers and by the arrangement of the pistillate flowers in single-flowered spikelets that are enclosed by the flask-like spikelet prophyll (utricle or perigynium). The nature of several morphological features of the Cariceae inflorescence remains controversial. The staminate reproductive units, as well as earlier reported bisexual reproductive units in Schoenoxiphium have been considered to be reduced partial inflorescences, or flowers. Aims of this study are to test both interpretat…
Prediction of lncRNA-Disease Associations from Tripartite Graphs
2021
The discovery of novel lncRNA-disease associations may provide valuable input to the understanding of disease mechanisms at lncRNA level, as well as to the detection of biomarkers for disease diagnosis, treatment, prognosis and prevention. Unfortunately, due to costs and time complexity, the number of possible disease-related lncRNAs verified by traditional biological experiments is very limited. Computational approaches for the prediction of potential disease-lncRNA associations can effectively decrease time and cost of biological experiments. We propose an approach for the prediction of lncRNA-disease associations based on neighborhood analysis performed on a tripartite graph, built upon …
Impacts écologiques des formes d'urbanisation : modélisations urbaines et paysagères
2015
The global increase of urbanization during the past decades have induced a progressive artificialization of natural environments. The building of transport infrastructures and new housings causes a landscape fragmentation in an irreversible way and a strong decrease of the connectivity of ecological habitats. Maintaining the functionality of ecological networks is becoming a major goal of sustainable urban planning policies. With a special focus on urban evolutions in the horizon 2030 in the urban area of Besançon in eastern France (residential development and road traffic evolutions), this thesis aims to assess the potential impact of urban forms on landscape connectivity of animal species…
Chromatic sums for colorings avoiding monochromatic subgraphs
2015
Abstract Given graphs G and H, a vertex coloring c : V ( G ) → N is an H-free coloring of G if no color class contains a subgraph isomorphic to H. The H-free chromatic number of G, χ ( H , G ) , is the minimum number of colors in an H-free coloring of G. The H-free chromatic sum of G , Σ ( H , G ) , is the minimum value achieved by summing the vertex colors of each H-free coloring of G. We provide a general bound for Σ ( H , G ) , discuss the computational complexity of finding this parameter for different choices of H, and prove an exact formulas for some graphs G. For every integer k and for every graph H, we construct families of graphs, G k with the property that k more colors than χ ( …
Decremental 2- and 3-connectivity on planar graphs
1996
We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log2n) time. This givesO(log2n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.
Le paysage, entre esthétique & écologie : modélisation rétrospective à partir de changements d'occupation du sol
2016
Landscape is both a backdrop to the lives of human populations and a medium for the life cycle of animal species. Landscape changes induced by land-use and land-cover dynamics affect both these dimensions, the one aesthetic, and the other ecological. Because these rationales areusually studied within different disciplines, little research has been done into how the two clashor combine as and when landscape structures change. This work seeks therefore to model the spatial co-evolution of the aesthetic and ecological functions of landscape retrospectively usingspatial metrics based on land-cover data. It focuses on changes in the urban fringes of two French cities (Paris and Besançon) over th…
Fillets:Cues for connections in Focus+Context views of graph-like diagrams
2003
We apply fillets-smoothing of sharp angles at the joints-between the connections and nodes of graph-like diagrams. In situations where the graph layout is constrained, e.g. Focus+Context views or views where the coordinates of the nodes are informative, fillets can clarify the relationships considerably without altering the layout. A visual search experiment supports our hypothesis that with fillets it is considerably easier to perceive node-connection structures. We discuss algorithms with different tradeoffs for flexibility and performance for rendering these connections in a single pass using OpenGL.
Conceptual graph operations for formal visual reasoning in the medical domain
2014
International audience; Objective - Conceptual graphs (CGs) are used to represent clinical guidelines because they support visual reasoning with a logical background, making them a potentially valuable representation for guidelines.Materials and methods - Conceptual graph formalism has an essential and basic component: a formal vocabulary that drives all of the other mechanisms, notably specialization and projection. The graph's theoretical operations, such as projection, rules, derivation, constraints, probabilities and uncertainty, support diagrammatic reasoning.Results - A conceptual graph's graphical user interface includes a multilingual vocabulary management, some query and decision-m…
Annealed Invariance Principle for Random Walks on Random Graphs Generated by Point Processes in R-d
2016
International audience; We consider simple random walks on random graphs embedded in R-d and generated by point processes such as Delaunay triangulations, Gabriel graphs and the creek-crossing graphs. Under suitable assumptions on the point process, we show an annealed invariance principle for these random walks. These results hold for a large variety of point processes including Poisson point processes, Matern cluster and Matern hardcore processes which have respectively clustering and repulsiveness properties. The proof relies on the use the process of the environment seen from the particle. It allows to reconstruct the original process as an additive functional of a Markovian process und…