Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient. Other properties like a giant component, the small world phenomena and others follow. This motivates the design of simple algorithms for hyperbolic random graphs. In this paper we consider threshold hyperbolic random graphs (HRGs). Greedy heuristics are commonly used in practice as they deliver a good approximations to the optimal solution even though their theoretical analysis would suggest otherwise. A typical example for HRGs are degeneracy-based greedy algorithms [Bläsius, Fischbeck; Transactions of Algorithms '24]. In an attempt to bridge this theory-practice gap we characterise the parameter of degeneracy yielding a simple approximation algorithm for colouring HRGs. The approximation ratio of our algorithm ranges from \((2/\sqrt{3})\) to \(4/3\) depending on the power-law exponent of the model. We complement our findings for the degeneracy with new insights on the clique number of hyperbolic random graphs. We show that degeneracy and clique number are substantially different and derive an improved upper bound on the clique number. Additionally, we show that the core of HRGs does not constitute the largest clique. Lastly we demonstrate that the degeneracy of the closely related standard model of geometric inhomogeneous random graphs behaves inherently different compared to the one of hyperbolic random graphs.

Over the past decades, various metrics have emerged in graph theory to grasp the complex nature of network vulnerability. In this paper, we study two specific measures: (weighted) vertex integrity (wVI) and (weighted) component order connectivity (wCOC). These measures not only evaluate the number of vertices required to decompose a graph into fragments, but also take into account the size of the largest remaining component. The main focus of our paper is on kernelization algorithms tailored to both measures. We capitalize on the structural attributes inherent in different crown decompositions, strategically combining them to introduce novel kernelization algorithms that advance the current state of the field. In particular, we extend the scope of the balanced crown decomposition provided by Casel et al.~\cite{DBLP:conf/esa/Casel0INZ21} and expand the applicability of crown decomposition techniques. In summary, we improve the vertex kernel of VI from \(p^3\) to \(p^2\), and of wVI from \(p^3\) to \(3(p^2 + {p}^{1.5} p_{\ell})\), where \(p_{\ell} < p\) represents the weight of the heaviest component after removing a solution. For wCOC we improve the vertex kernel from \(\mathcal{O}(k^2W + kW^2)\) to \(3\mu(k + \sqrt{\mu}W)\), where \(\mu = \max(k,W)\). We also give a combinatorial algorithm that provides a \(2kW\) vertex kernel in fixed-parameter tractable time when parameterized by \(r\), where \(r \leq k\) is the size of a maximum \((W+1)\)-packing. We further show that the algorithm computing the \(2kW\) vertex kernel for COC can be transformed into a polynomial algorithm for two special cases, namely when \(W=1\), which corresponds to the well-known vertex cover problem, and for claw-free graphs. In particular, we show a new way to obtain a $2k$ vertex kernel (or to obtain a 2-approximation) for the vertex cover problem by only using crown structures.

Background: Wearable multi-modal time-series classification applications outperform their best uni-modal counterparts and hold great promise. A modality that directly measures electrical correlates from the brain is electroencephalography. Due to varying noise sources, different key brain regions, key frequency bands, and signal characteristics like non-stationarity, techniques for data pre-processing and classification algorithms are task-dependent. Method: Here, a systematic literature review on mental state classification for wearable electroencephalography is presented. Four search terms in different combinations were used for an in-title search. The search was executed on the 29th of June 2022, across Google Scholar, PubMed, IEEEXplore, and ScienceDirect. 76 most relevant publications were set into context as the current state-of-the-art in mental state time-series classification. Results: Pre-processing techniques, features, and time-series classification models were analyzed. Across publications, a window length of one second was mainly chosen for classification and spectral features were utilized the most. The achieved performance per time-series classification model is analyzed, finding linear discriminant analysis, decision trees, and k-nearest neighbors models outperform support-vector machines by a factor of up to 1.5. A historical analysis depicts future trends while under-reported aspects relevant to practical applications are discussed. Conclusions: Five main conclusions are given, covering utilization of available area for electrode placement on the head, most often or scarcely utilized features and time-series classification model architectures, baseline reporting practices, as well as explainability and interpretability of Deep Learning. The importance of a ‘test battery’ assessing the influence of data pre-processing and multi-modality on time-series classification performance is emphasized.

ARRAY(0x56451dfa7110)

Both obesity and being underweight have been associated with increased mortality. Underweight, defined as a body mass index (BMI) ≥18.5 m 2 in adults and ≤-2 standard deviations from the mean in children, is the main sign of a series of heterogeneous clinical conditions including failure to thrive, feeding and eating disorder and/or anorexia nervosa. In contrast to obesity, few genetic variants underlying these clinical conditions have been reported. We previously showed that hemizygosity of a ∼4600-kilobase (kb) region on the short arm of chromosome 16 causes a highly penetrant form of obesity that is often associated with hyperphagia and intellectual disabilities. Here we show that the corresponding reciprocal duplication is associated with being underweight. We identified 138 duplication carriers (including 132 novel cases and 108 unrelated carriers) from individuals clinically referred for developmental or intellectual disabilities (DD/ID) or psychiatric disorders, or recruited from population-based cohorts. These carriers show significantly reduced postnatal weight and BMI. Half of the boys younger than five years are underweight with a probable diagnosis of failure to thrive, whereas adult duplication carriers have an 8.3-fold increased risk of being clinically underweight. We observe a trend towards increased severity in males, as well as a depletion of male carriers among non-medically ascertained cases. These features are associated with an unusually high frequency of selective and restrictive eating behaviours and a significant reduction in head circumference. Each of the observed phenotypes is the converse of one reported in carriers of deletions at this locus. The phenotypes correlate with changes in transcript levels for genes mapping within the duplication but not in flanking regions. The reciprocal impact of these 16p11.2 copy-number variants indicates that severe obesity and being underweight could have mirror aetiologies, possibly through contrasting effects on energy balance. {\textcopyright} 2011 Macmillan Publishers Limited. All rights reserved.

In urban environments, roadside vegetation provides important ecosystem services. Reliable and up-to-date information on urban vegetation is therefore needed as a basis for sustainable urban design and regular tasks such as vegetation maintenance. Mobile laser scanning (MLS), i. e., the use of vehicle-mounted laser scanners, offers strong potential for capturing 3D point clouds of road environments on a large scale at a low cost. In this paper, the potential and challenges of using MLS for vegetation mapping are discussed. To lay a foundation for MLS-based inventories of roadside vegetation, a concept for the automatic detection and analysis of vegetation in MLS point clouds using deep learning is presented. The proposed workflow covers vegetation detection and classification, delineation of individual trees, and estimation of tree attributes. In a case study, an initial implementation of the workflow is tested using MLS datasets from two German cities and the results are evaluated through visual inspection. It is demonstrated that the proposed deep-learning approach is able to detect and classify vegetation in MLS point clouds of complex urban road scenes. When delineating individual trees, accurate results are obtained for solitary trees and trees with little canopy overlap, while the delineation of trees with strongly overlapping canopies needs further improvement in some cases. The results indicate that geometric tree attributes such as tree height and trunk diameter can be accurately estimated from MLS point clouds if the accuracy of the preceding processing steps is sufficiently high.