Thunderclap headache attributed to reversible cerebral vasoconstriction: view and review

Thunderclap headache attributed to reversible cerebral vasoconstriction (THARCV) is a syndrome observed in a number of reported cases. In this article we reviewed this new headache entity (idiopathic form) using the clinical-radiological findings of 25 reported patients. In this series of patients 72% were women, the mean age at the onset of first headache episode was 39.4 +/- 2.3 years. In addition to the sine quanon condition of being abrupt and severe (thunderclap) at the onset, the headache was usually described as being explosive, excruciating, or crushing. The feature of pulsatility, accompanied or not by nausea was described by 80% of the patients. Forty percent of the cases manifested vomiting and 24% photophobia. Usually the headache was generalized, and in three cases it was unilateral at least at the onset. In 21 of 25 patients (84%) there was at least one recurrence or a sudden increase in the intensity of the headache. A past history of migraine was present in 52% of the patients. Precipitating factors were identified in 56% of the patients. Sexual intercourse was described by six patients. Of the 25 patients with THARCV syndrome studied, 12 (48%) developed focal neurological signs, transitory ischemic attack (n = 1), or ischemic stroke (n = 11, 44%), and two (8%) of them manifested seizures. The THARCV syndrome is a neurological disturbance perhaps more frequent than expected, preferentially affecting middle aged female migraineurs, and having an unpredictable prognosis, either showing a benign course or leading to stroke.

Numerical evidence against a conjecture on the cover time of planar graphs

We investigate a conjecture on the cover times of planar graphs by means of large Monte Carlo simulations. The conjecture states that the cover time tau (G(N)) of a planar graph G(N) of N vertices and maximal degree d is lower bounded by tau (G(N)) >= C(d)N(lnN)(2) with C(d) = (d/4 pi) tan(pi/d), with equality holding for some geometries. We tested this conjecture on the regular honeycomb (d = 3), regular square (d = 4), regular elongated triangular (d = 5), and regular triangular (d = 6) lattices, as well as on the nonregular Union Jack lattice (d(min) = 4, d(max) = 8). Indeed, the Monte Carlo data suggest that the rigorous lower bound may hold as an equality for most of these lattices, with an interesting issue in the case of the Union Jack lattice. The data for the honeycomb lattice, however, violate the bound with the conjectured constant. The empirical probability distribution function of the cover time for the square lattice is also briefly presented, since very little is known about cover time probability distribution functions in general.

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.

On the resilience of long cycles in random graphs

In this paper we determine the local and global resilience of random graphs G(n,p) (p >> n(-1)) with respect to the property of containing a cycle of length at least (1 - alpha)n. Roughly speaking, given alpha > 0, we determine the smallest r(g) (G, alpha) with the property that almost surely every subgraph of G = G(n,p) having more than r(g) (G, alpha)vertical bar E(G)vertical bar edges contains a cycle of length at least (1 - alpha)n (global resilience). We also obtain, for alpha < 1/2, the smallest r(l) (G, alpha) such that any H subset of G having deg(H) (v) larger than r(l) (G, alpha) deg(G) (v) for all v is an element of V(G) contains a cycle of length at least (1 - alpha)n (local resilience). The results above are in fact proved in the more general setting of pseudorandom graphs.

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]

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.

Texture analysis using graphs generated by deterministic partially self-avoiding walks

Texture is one of the most important visual attributes for image analysis. It has been widely used in image analysis and pattern recognition. A partially self-avoiding deterministic walk has recently been proposed as an approach for texture analysis with promising results. This approach uses walkers (called tourists) to exploit the gray scale image contexts in several levels. Here, we present an approach to generate graphs out of the trajectories produced by the tourist walks. The generated graphs embody important characteristics related to tourist transitivity in the image. Computed from these graphs, the statistical position (degree mean) and dispersion (entropy of two vertices with the same degree) measures are used as texture descriptors. A comparison with traditional texture analysis methods is performed to illustrate the high performance of this novel approach. (C) 2011 Elsevier Ltd. All rights reserved.

Structural matching of 2D electrophoresis gels using deformed graphs

2D electrophoresis is a well-known method for protein separation which is extremely useful in the field of proteomics. Each spot in the image represents a protein accumulation and the goal is to perform a differential analysis between pairs of images to study changes in protein content. It is thus necessary to register two images by finding spot correspondences. Although it may seem a simple task, generally, the manual processing of this kind of images is very cumbersome, especially when strong variations between corresponding sets of spots are expected (e.g. strong non-linear deformations and outliers). In order to solve this problem, this paper proposes a new quadratic assignment formulation together with a correspondence estimation algorithm based on graph matching which takes into account the structural information between the detected spots. Each image is represented by a graph and the task is to find a maximum common subgraph. Successful experimental results using real data are presented, including an extensive comparative performance evaluation with ground-truth data. (C) 2010 Elsevier B.V. All rights reserved.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Performance evaluation of routing protocols for MANETs with known connectivity patterns using evolving graphs

The assessment of routing protocols for mobile wireless networks is a difficult task, because of the networks` dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and some delay tolerant networks (DTNs), have more predictable dynamics, as the temporal variations in the network topology can be considered as deterministic, which may make them easier to study. Recently, a graph theoretic model-the evolving graphs-was proposed to help capture the dynamic behavior of such networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study about the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we use the NS2 network simulator to first implement an evolving graph based routing protocol, and then to use it as a benchmark when comparing the four major ad hoc routing protocols (AODV, DSR, OLSR and DSDV). Interestingly, our experiments show that evolving graphs have the potential to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like adaptive algorithms. We also discuss such issues in this paper, as a result of our experience.

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M = (V, E, A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C = {C(1), ... , C(k)} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is Sigma(k)(i=1) vertical bar C(i)vertical bar. The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2 + epsilon, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs. (C) 2007 Elsevier B.V. All rights reserved.

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.