Search

Given an undirected graph G on n nodes and m edges in the form of a data stream we study the problem of finding an Euler tour in G. Our main result is the first one-pass streaming algorithm computing an Euler tour of G in the form of an edge successor function with only $\mathcal O(n\log (n))$ O ( n log ( n ) ) RAM, which is optimal for this setting (e.g. Sun and Woodruff (2015)). Since the output size can be much larger, we use a write-only tape to gradually output the solution. The previously best-known result for finding Euler tours in data streams is implicitly given by the W-stream algorithm of Demetrescu et al. (2010) using $\mathcal O(m/n)$ O ( m / n ) passes under the same RAM limitation. Our approach is to partition the edges into edge-disjoint cycles and to merge the cycles until a single Euler tour is achieved. In the streaming environment such a merging is far from being obvious as the limited RAM allows the processing of only a constant number of cycles at once. This enforces merging of cycles that partially are no longer present in RAM. We solve this problem with a new edge swapping technique, for which storing two certain edges per node is sufficient to merge tours without having all tour edges in RAM. The mathematical key is to model tours and their merging in an algebraic way, where certain equivalence classes represent subtours. This quite general approach might be of interest also in other routing problems.

Objective Childhood absence epilepsy (CAE) is a disease with distinct seizure semiology and electroencephalographic (EEG) features. Differentiating ictal and subclinical generalized spikes and waves discharges (GSWDs) in the EEG is challenging, since they appear to be identical upon visual inspection. Here, spectral and functional connectivity (FC) analyses were applied to routine EEG data of CAE patients, to differentiate ictal and subclinical GSWDs. Methods Twelve CAE patients with both ictal and subclinical GSWDs were retrospectively selected for this study. The selected EEG epochs were subjected to frequency analysis in the range of 1–30 Hz. Further, FC analysis based on the imaginary part of coherency was used to determine sensor level networks. Results Delta, alpha and beta band frequencies during ictal GSWDs showed significantly higher power compared to subclinical GSWDs. FC showed significant network differences for all frequency bands, demonstrating weaker connectivity between channels during ictal GSWDs. Conclusion Using spectral and FC analyses significant differences between ictal and subclinical GSWDs in CAE patients were detected, suggesting that these features could be used for machine learning classification purposes to improve EEG monitoring. Significance Identifying differences between ictal and subclinical GSWDs using routine EEG, may improve understanding of this syndrome and the management of patients with CAE.

Childhood absence epilepsy (CAE), involves 3 Hz generalized spikes and waves discharges (GSWDs) on the electroencephalogram (EEG), associated with ictal discharges (seizures) with clinical symptoms and impairment of consciousness and subclinical discharges without any objective clinical symptoms or impairment of consciousness. This study aims to comparatively characterize neuronal networks underlying absence seizures and subclinical discharges, using source localization and functional connectivity (FC), to better understand the pathophysiological mechanism of these discharges. Routine EEG data from 12 CAE patients, consisting of 45 ictal and 42 subclinical discharges were selected. Source localization was performed using the exact low-resolution electromagnetic tomography (eLORETA) algorithm, followed by FC based on the imaginary part of coherency. FC based on the thalamus as the seed of interest showed significant differences between ictal and subclinical GSWDs (p

For a given b ∈ N n and a hypergraph H = ( V , E ) with maximum degree Δ, the b-set multicover problem which we are concerned with in this paper may be stated as follows: find a minimum cardinality subset C ⊆ E such that no vertex v i ∈ V is contained in less than b i hyperedges of C . Peleg, Schechtman, and Wool (1997) conjectured that for any fixed Δ and b = min i ⁡ b i , the problem cannot be approximated with a ratio strictly smaller than δ : = Δ − b + 1 , unless P = NP . In this paper, we show that the conjecture of Peleg et al. is not true on l-uniform hypergraphs by presenting a polynomial-time approximation algorithm based on a matching/covering duality for hypergraphs due to Ray-Chaudhuri (1960), which we convert into an approximative form. The given algorithm yields a ratio smaller than ( 1 − b ( l + 1 ) Δ ) Δ b . Moreover, we prove that the lower bound conjectured by Peleg et al. holds for regular hypergraphs under the unique games conjecture.

De novo genome assembly is a fundamental task in life sciences. It is mostly a typical big data problem with sometimes billions of reads, a big puzzle in which the genome is hidden. Memory and time efficient algorithms are sought, preferably to run even on desktops in labs. In this chapter we address some algorithmic problems related to genome assembly. We first present an algorithm which heavily reduces the size of input data, but with no essential compromize on the assembly quality. In such and many other algorithms in bioinformatics the counting of k-mers is a botleneck. We discuss counting in external memory. The construction of large parts of the genome, called contigs, can be modelled as the longest path problem or the Euler tour problem in some graphs build on reads or k-mers. We present a linear time streaming algorithm for constructing long paths in undirected graphs, and a streaming algorithm for the Euler tour problem with optimal one-pass complexity.

In this paper, a new class of hemivariational inequalities is introduced. It concerns Laplace operator on locally finite graphs together with multivalued nonmonotone nonlinearities expressed in terms of Clarke's subdifferential. First of all, we state and prove some results on the subdifferentiability of nonconvex functionals defined on graphs. Thereafter, an elliptic hemivariational inequality on locally finite graphs is considered and the existence and uniqueness of its weak solutions are proved by means of the well-known surjectivity result for pseudomonotone mappings. In the end of this paper, we tackle the problem of hemivariational inequalities of parabolic type on locally finite graphs and we prove the existence of its weak solutions., Comment: 23 pages

Let $$\mathcal {H}=(V,\mathcal {E})$$ be a hypergraph with maximum edge size $$\ell $$ and maximum degree $$\varDelta $$ . For a given positive integers $$b_v$$ , $$v\in V$$ , a set multicover in $$\mathcal {H}$$ is a set of edges $$C \subseteq \mathcal {E}$$ such that every vertex v in V belongs to at least $$b_v$$ edges in C. Set multicover is the problem of finding a minimum-cardinality set multicover. Peleg, Schechtman and Wool conjectured that for any fixed $$\varDelta $$ and $$b:=\min _{v\in V}b_{v}$$ , the problem of set multicover is not approximable within a ratio less than $$\delta :=\varDelta -b+1$$ , unless $$\mathcal {P}=\mathcal {NP}$$ . Hence it’s a challenge to explore for which classes of hypergraph the conjecture doesn’t hold. We present a polynomial time algorithm for the set multicover problem which combines a deterministic threshold algorithm with conditioned randomized rounding steps. Our algorithm yields an approximation ratio of $$\max \left\{ \frac{148}{149}\delta , \left( 1- \frac{ (b-1)e^{\frac{\delta }{4}}}{94\ell } \right) \delta \right\} $$ for $$b\ge 2$$ and $$\delta \ge 3$$ . Our result not only improves over the approximation ratio presented by El Ouali et al. (Algorithmica 74:574, 2016) but it’s more general since we set no restriction on the parameter $$\ell $$ . Moreover we present a further polynomial time algorithm with an approximation ratio of $$\frac{5}{6}\delta $$ for hypergraphs with $$\ell \le (1+\epsilon )\bar{\ell }$$ for any fixed $$\epsilon \in [0,\frac{1}{2}]$$ , where $$\bar{\ell }$$ is the average edge size. The analysis of this algorithm relies on matching/covering duality due to Ray-Chaudhuri (1960), which we convert into an approximative form. The second performance disprove the conjecture of Peleg et al. for a large subclass of hypergraphs.