On the k-restricted structure ratio in planar and outerplanar graphs

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work. The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version. Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.

An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

TESTING STATISTICAL HYPOTHESIS ON RANDOM TREES AND APPLICATIONS TO THE PROTEIN CLASSIFICATION PROBLEM

Efficient automatic protein classification is of central importance in genomic annotation. As an independent way to check the reliability of the classification, we propose a statistical approach to test if two sets of protein domain sequences coming from two families of the Pfam database are significantly different. We model protein sequences as realizations of Variable Length Markov Chains (VLMC) and we use the context trees as a signature of each protein family. Our approach is based on a Kolmogorov-Smirnov-type goodness-of-fit test proposed by Balding et at. [Limit theorems for sequences of random trees (2008), DOI: 10.1007/s11749-008-0092-z]. The test statistic is a supremum over the space of trees of a function of the two samples; its computation grows, in principle, exponentially fast with the maximal number of nodes of the potential trees. We show how to transform this problem into a max-flow over a related graph which can be solved using a Ford-Fulkerson algorithm in polynomial time on that number. We apply the test to 10 randomly chosen protein domain families from the seed of Pfam-A database (high quality, manually curated families). The test shows that the distributions of context trees coming from different families are significantly different. We emphasize that this is a novel mathematical approach to validate the automatic clustering of sequences in any context. We also study the performance of the test via simulations on Galton-Watson related processes.

Gibbs random graphs on point processes

Consider a discrete locally finite subset Gamma of R(d) and the cornplete graph (Gamma, E), with vertices Gamma and edges E. We consider Gibbs measures on the set of sub-graphs with vertices Gamma and edges E` subset of E. The Gibbs interaction acts between open edges having a vertex in common. We study percolation properties of the Gibbs distribution of the graph ensemble. The main results concern percolation properties of the open edges in two cases: (a) when Gamma is sampled from a homogeneous Poisson process; and (b) for a fixed Gamma with sufficiently sparse points. (c) 2010 American Institute of Physics. [doi:10.1063/1.3514605]

An oracle approach for interaction neighborhood estimation in random fields

We consider the problem of interaction neighborhood estimation from the partial observation of a finite number of realizations of a random field. We introduce a model selection rule to choose estimators of conditional probabilities among natural candidates. Our main result is an oracle inequality satisfied by the resulting estimator. We use then this selection rule in a two-step procedure to evaluate the interacting neighborhoods. The selection rule selects a small prior set of possible interacting points and a cutting step remove from this prior set the irrelevant points. We also prove that the Ising models satisfy the assumptions of the main theorems, without restrictions on the temperature, on the structure of the interacting graph or on the range of the interactions. It provides therefore a large class of applications for our results. We give a computationally efficient procedure in these models. We finally show the practical efficiency of our approach in a simulation study.

The Lobel-Komlos-Sos conjecture for trees of diameter 5 and for certain caterpillars

Loebl, Komlos, and Sos conjectured that if at least half the vertices of a graph G have degree at least some k is an element of N, then every tree with at most k edges is a subgraph of G. We prove the conjecture for all trees of diameter at most 5 and for a class of caterpillars. Our result implies a bound on the Ramsey number r( T, T') of trees T, T' from the above classes.

Morpholin-4-ium morpholine-4-carbodithioate

The title compound, C(4)H(10)NO(+)center dot C(5)H(8)NOS(2)(-), is built up of a morpholinium cation and a dithiocarbamate anion. In the crystal, two structurally independent formula units are linked via N-H center dot center dot center dot S hydrogen bonds, forming an inversion dimer, with graph-set motif R(4)(4)(12).

Skewness, splitting number and vertex deletion of some toroidal meshes

The skewness sk(G) of a graph G = (V, E) is the smallest integer sk(G) >= 0 such that a planar graph can be obtained from G by the removal of sk(C) edges. The splitting number sp(G) of C is the smallest integer sp(G) >= 0 such that a planar graph can be obtained from G by sp(G) vertex splitting operations. The vertex deletion vd(G) of G is the smallest integer vd(G) >= 0 such that a planar graph can be obtained from G by the removal of vd(G) vertices. Regular toroidal meshes are popular topologies for the connection networks of SIMD parallel machines. The best known of these meshes is the rectangular toroidal mesh C(m) x C(n) for which is known the skewness, the splitting number and the vertex deletion. In this work we consider two related families: a triangulation Tc(m) x c(n) of C(m) x C(n) in the torus, and an hexagonal mesh Hc(m) x c(n), the dual of Tc(m) x c(n) in the torus. It is established that sp(Tc(m) x c(n)) = vd(Tc(m) x c(n) = sk(Hc(m) x c(n)) = sp(Hc(m) x c(n)) = vd(Hc(m) x c(n)) = min{m, n} and that sk(Tc(m) x c(n)) = 2 min {m, n}.

Node-Depth Encoding and Multiobjective Evolutionary Algorithm Applied to Large-Scale Distribution System Reconfiguration

The power loss reduction in distribution systems (DSs) is a nonlinear and multiobjective problem. Service restoration in DSs is even computationally hard since it additionally requires a solution in real-time. Both DS problems are computationally complex. For large-scale networks, the usual problem formulation has thousands of constraint equations. The node-depth encoding (NDE) enables a modeling of DSs problems that eliminates several constraint equations from the usual formulation, making the problem solution simpler. On the other hand, a multiobjective evolutionary algorithm (EA) based on subpopulation tables adequately models several objectives and constraints, enabling a better exploration of the search space. The combination of the multiobjective EA with NDE (MEAN) results in the proposed approach for solving DSs problems for large-scale networks. Simulation results have shown the MEAN is able to find adequate restoration plans for a real DS with 3860 buses and 632 switches in a running time of 0.68 s. Moreover, the MEAN has shown a sublinear running time in function of the system size. Tests with networks ranging from 632 to 5166 switches indicate that the MEAN can find network configurations corresponding to a power loss reduction of 27.64% for very large networks requiring relatively low running time.

Assembling a consistent set of sentences in relational probabilistic logic with stochastic independence

We examine the representation of judgements of stochastic independence in probabilistic logics. We focus on a relational logic where (i) judgements of stochastic independence are encoded by directed acyclic graphs, and (ii) probabilistic assessments are flexible in the sense that they are not required to specify a single probability measure. We discuss issues of knowledge representation and inference that arise from our particular combination of graphs, stochastic independence, logical formulas and probabilistic assessments. (C) 2007 Elsevier B.V. All rights reserved.

Probabilistic logic with independence

This paper investigates probabilistic logics endowed with independence relations. We review propositional probabilistic languages without and with independence. We then consider graph-theoretic representations for propositional probabilistic logic with independence; complexity is analyzed, algorithms are derived, and examples are discussed. Finally, we examine a restricted first-order probabilistic logic that generalizes relational Bayesian networks. (c) 2007 Elsevier Inc. All rights reserved.

Exploring the random genesis of co-occurrence networks

Using the network random generation models from Gustedt (2009)[23], we simulate and analyze several characteristics (such as the number of components, the degree distribution and the clustering coefficient) of the generated networks. This is done for a variety of distributions (fixed value, Bernoulli, Poisson, binomial) that are used to control the parameters of the generation process. These parameters are in particular the size of newly appearing sets of objects, the number of contexts in which new elements appear initially, the number of objects that are shared with `parent` contexts, and, the time period inside which a context may serve as a parent context (aging). The results show that these models allow to fine-tune the generation process such that the graphs adopt properties as can be found in real world graphs. (C) 2011 Elsevier B.V. All rights reserved.

Characterization of electrical penetration graphs of the Asian citrus psyllid, Diaphorina citri, in sweet orange seedlings

Detailed information on probing behavior of the Asian citrus psyllid, Diaphorina citri Kuwayama (Hemiptera: Psyllidae), is critical for understanding the transmission process of phloem-limited bacteria (Candidatus Liberibacter spp.) associated with citrus `huanglongbing` by this vector. In this study, we investigated stylet penetration activities of D. citri on seedlings of Citrus sinensis (L.) Osbeck cv. Pera (Rutaceae) by using the electrical penetration graph (EPG-DC system) technique. EPG waveforms were described based on amplitude, frequency, voltage level, and electrical origin of the observed traces during stylet penetration into plant tissues. The main waveforms were correlated with histological observations of salivary sheath termini in plant tissues, to determine the putative location of stylet tips. The behavioral activities were also inferred based on waveform similarities in relation to other Sternorrhyncha, particularly aphids and whiteflies. In addition, we correlated the occurrence of specific waveforms with the acquisition of the phloem-limited bacterium Ca. Liberibacter asiaticus by D. citri. The occurrence of a G-like xylem sap ingestion waveform in starved and unstarved psyllids was also compared. By analyzing 8-h EPGs of adult females, five waveforms were described: (C) salivary sheath secretion and other stylet pathway activities; (D) first contact with phloem (distinct from other waveforms reported for Sternorrhyncha); (E1) putative salivation in phloem sieve tubes; (E2) phloem sap ingestion; and (G) probably xylem sap ingestion. Diaphorina citri initiates a probe with stylet pathway through epidermis and parenchyma (C). Interestingly, no potential drops were observed during the stylet pathway phase, as are usually recorded in aphids and other Sternorrhyncha. Once in C, D. citri shows a higher propensity to return to non-probing than to start a phloem or xylem phase. Several probes are usually observed before the phloem phase; waveform D is observed upon phloem contact, always immediately followed by E1. After E1, D. citri either returns to pathway activity (C) or starts phloem sap ingestion, which was the longest activity observed.

Characterization of electrical penetration graphs of Bucephalogonia xanthophis, a vector of Xylella fastidiosa in citrus

The sharpshooter Bucephalogonia xanthophis (Berg) (Homoptera: Cicadellidae) is a vector of the xylem-limited bacterium, Xylella fastidiosa (Wells, Raju, Hung, Weisburg, Mandelco-Paul, and Brenner), which causes citrus variegated chlorosis. Despite the importance of citrus variegated chlorosis, the probing behavior of vectors on citrus and its implications for transmission of X. fastidiosa have not been studied. Here we studied electrical penetration graph (EPG-DC system) waveforms produced by B. xanthophis on Citrus sinensis (L.) Osbeck (Rutaceae), and their relationships with stylet activities and xylem ingestion. Electrical penetration graph waveforms were described based on amplitude, frequency, voltage level, and electrical origin of the observed traces during stylet penetration on plant tissues. The main waveforms were correlated with histological observations of salivary sheaths in plant tissues and excretion analysis, in order to determine stylet activities and their precise position. Six waveforms and associated activities are described: (S) secretion of salivary sheath and intracellular stylet pathway, (R) resting during stylet pathway, (Xc) contact of stylets with xylem vessels, (Xi) active xylem ingestion, (N) interruption within the xylem phase (during Xc or Xi), and (W) withdrawal of stylet from the plant. The sharpshooter spent 91.8% of its probing time with its stylet in the xylem, where the main activity was ingestion (Xi: 97.5%). During a probe, the most likely sequence of events is secretion of salivary sheath and pathway (S) through epidermal and parenchyma cells (all individuals), followed by contact with xylem (Xc) (67.6% of all individuals) and ingestion (Xi) (88.3% of those that exhibit waveform Xc). The mean time to contact the xylem (Xc) and initiate ingestion (Xi) after onset of the first probe was 27.8 and 34.2 min, respectively. However, sustained xylem ingestion (Xi > 5 min) was established after 39.8 min, on average. This information is basic for future studies on the transmission mechanisms of X. fastidiosa and in order to establish control strategies aimed at interfering with this process.

Optimal irrigation depth for bean crops considering water constraints and farmer`s risk aversion level

Nowadays, the rising competition for the use of water and environmental resources with consequent restrictions for farmers should change the paradigm in terms of irrigation concepts, or rather, in order to attain economical efficiency other than to supply water requirement for the crop. Therefore, taking into account the social and economical role of bean activity in Brazil, as well as the risk inherent to crop due to its high sensibility to both deficit and excessive water, the optimization methods regarding to irrigation management have become more interesting and essential. This study intends to present a way to determine the optimal water supply, considering different combinations between desired bean yield and level of risk, bringing as a result a graph with the former associated with the latter, depending on different water depths.