93 research outputs found
Cluster Deletion on Interval Graphs and Split Related Graphs
No full textIn the Cluster Deletion problem the goal is to remove the minimum number of edges of a given graph, such that every connected component of the resulting graph constitutes a clique. It is known that the decision version of Cluster Deletion is NP-complete on (P_5-free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of Cluster Deletion on interval graphs, a proper subclass of chordal graphs, remained a well-known open problem. Our main contribution is that we settle this problem in the affirmative, by providing a polynomial-time algorithm for Cluster Deletion on interval graphs. Moreover, despite the simple formulation of the algorithm on split graphs, we show that Cluster Deletion remains NP-complete on a natural and slight generalization of split graphs that constitutes a proper subclass of P_5-free chordal graphs. Although the later result arises from the already-known reduction for P_5-free chordal graphs, we give an alternative proof showing an interesting connection between edge-weighted and vertex-weighted variations of the problem. To complement our results, we provide faster and simpler polynomial-time algorithms for Cluster Deletion on subclasses of such a generalization of split graphs
Maximizing the Strong Triadic Closure in Split Graphs and Proper Interval Graphs
No full textIn social networks the Strong Triadic Closure is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which the problem is solvable. We show that the problem admits a polynomial-time algorithm for two unrelated classes of graphs: proper interval graphs and trivially-perfect graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal graphs. Thus we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete
Parameterized Aspects of Strong Subgraph Closure
No full textMotivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the Strong F-closure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of F-free Edge Deletion. In Strong F-closure, we want to select a maximum number of edges of the input graph G, and mark them as strong edges, in the following way: whenever a subset of the strong edges forms a subgraph isomorphic to F, then the corresponding induced subgraph of G is not isomorphic to F. Hence the subgraph of G defined by the strong edges is not necessarily F-free, but whenever it contains a copy of F, there are additional edges in G to destroy that strong copy of F in G.
We study Strong F-closure from a parameterized perspective with various natural parameterizations. Our main focus is on the number k of strong edges as the parameter. We show that the problem is FPT with this parameterization for every fixed graph F, whereas it does not admit a polynomial kernel even when F =P_3. In fact, this latter case is equivalent to the Strong Triadic Closure problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that Strong Triadic Closure does not admit a polynomial kernel even when the input graph is a split graph, whereas it admits a polynomial kernel when the input graph is planar, and even d-degenerate. Furthermore, on graphs of maximum degree at most 4, we show that Strong Triadic Closure is FPT with the above guarantee parameterization k - mu(G), where mu(G) is the maximum matching size of G. We conclude with some results on the parameterization of Strong F-closure by the number of edges of G that are not selected as strong
Development of a Detection and Tracking of Moving Vehicles system for 2D LIDAR sensors
No full textThe main objective of this thesis was the development and evaluation of a Detection and Tracking of Moving Objects (DATMO) system, that is capable of reliably tracking nearby vehicles from a moving car. The developed system takes in raw 2D LIght Detection And Ranging (LIDAR) measurements as input and detects objects of interest by clustering them with the Adaptive Breakpoint Detector algorithm. The resulting clusters are fitted with oriented bounding boxes, by incorporating the Search-Based Rectangle Fitting algorithm. The tracking part of the system receives, extracted from the rectangles, L-shapes and associates them with already tracked vehicles, using the Global Nearest Neighbor algorithm. However, since LIDAR measures only the distance to surfaces that face the sensor, vehicle appearances change over time. In order to counteract tracking errors that originate from these changes, an L-shape switching algorithm is implemented. The kinematic poses of the tracked vehicles are estimated with two different tracking filters, a Kalman Filter (KF), with a constant velocity model and an Unscented Kalman Filter (UKF), with a Coordinated Turn kinematic model. The dimensions of the detected vehicles are estimated with a constant shape Kalman Filter. The proposed system was evaluated using both simulation and real-world experiments. The real-world experiments were made on the Delft Scaled Vehicle (DSV), an experimental car platform in the form of a 1/10 scale radio controlled car, and the ground truth data were provided by a Motion Capture (MoCap) system. The simulation experiments were made in a highway environment, which was created specifically for the development and testing of this system. Evaluating the experiment results reveals that the developed system can reliably estimate the position, speed, heading angle and dimensions of surrounding vehicles and therefore it can be used in similar research platforms to expand their environment perception capabilities.Mechanical Engineering | Systems and Contro
A Content-Based Publish/Subscribe Matching Algorithm for 2D Spatial Objects
No full textPart 5: Notification and StreamingInternational audienceAn important concern in the design of a publish/subscribe system is its expressiveness, which is the ability to represent various types of information in publications and to precisely select information of interest through subscriptions. We present an enhancement to existing content-based publish/subscribe systems with support for a 2D spatial data type and eight associated relational operators, including those to reveal overlap, containment, touching, and disjointedness between regions of irregular shape. We describe an algorithm for evaluating spatial relations that is founded on a new dynamic discretization method and region-intersection model. In order to make the data type practical for large-scale applications, we provide an indexing structure for accessing spatial constraints and develop a simplification method for eliminating redundant constraints. Finally, we present the results of experiments evaluating the effectiveness and scalability of our approach
New insights from the biogas microbiome by comprehensive genome-resolved metagenomics of nearly 1600 species originating from multiple anaerobic digesters
No full textCampanaro S, Treu L, Rodriguez-R LM, et al. New insights from the biogas microbiome by comprehensive genome-resolved metagenomics of nearly 1600 species originating from multiple anaerobic digesters. Biotechnology for Biofuels. 2020;13: 25.Background: Microorganisms in biogas reactors are essential for degradation of organic matter and methane production. However, a comprehensive genome-centric comparison, including relevant metadata for each sample, is still needed to identify the globally distributed biogas community members and serve as a reliable repository.; Results: Here, 134 publicly available metagenomes derived from different biogas reactors were used to recover 1635 metagenome-assembled genomes (MAGs) representing different biogas bacterial and archaeal species. All genomes were estimated to be >50% complete and nearly half ≥90% complete with ≤5% contamination. In most samples, specialized microbial communities were established, while only a few taxa were widespread among the different reactor systems. Metabolic reconstruction of the MAGs enabled the prediction of functional traits related to biomass degradation and methane production from waste biomass. An extensive evaluation of the replication index provided an estimation of the growth dynamics for microbes involved in different steps of the food chain.; Conclusions: The outcome of this study highlights a high flexibility of the biogas microbiome, allowing it to modify its composition and to adapt to the environmental conditions, including temperatures and a wide range of substrates. Our findings enhance our mechanistic understanding of the AD microbiome and substantially extend the existing repository of genomes. The established database represents a relevant resource for future studies related to this engineered ecosystem. © The Author(s) 2020
A Content-Based Publish/Subscribe Matching Algorithm for 2D Spatial Objects
No full textPart 5: Notification and StreamingInternational audienceAn important concern in the design of a publish/subscribe system is its expressiveness, which is the ability to represent various types of information in publications and to precisely select information of interest through subscriptions. We present an enhancement to existing content-based publish/subscribe systems with support for a 2D spatial data type and eight associated relational operators, including those to reveal overlap, containment, touching, and disjointedness between regions of irregular shape. We describe an algorithm for evaluating spatial relations that is founded on a new dynamic discretization method and region-intersection model. In order to make the data type practical for large-scale applications, we provide an indexing structure for accessing spatial constraints and develop a simplification method for eliminating redundant constraints. Finally, we present the results of experiments evaluating the effectiveness and scalability of our approach
Inferring Tie Strength in Temporal Networks
No full textInferring tie strengths in social networks is an essential task in social
network analysis. Common approaches classify the ties as wea} and strong ties
based on the strong triadic closure (STC). The STC states that if for three
nodes, , , and , there are strong ties between and , as well as
and , there has to be a (weak or strong) tie between and . A
variant of the STC called STC+ allows adding a few new weak edges to obtain
improved solutions. So far, most works discuss the STC or STC+ in static
networks. However, modern large-scale social networks are usually highly
dynamic, providing user contacts and communications as streams of edge updates.
Temporal networks capture these dynamics. To apply the STC to temporal
networks, we first generalize the STC and introduce a weighted version such
that empirical a priori knowledge given in the form of edge weights is
respected by the STC. Similarly, we introduce a generalized weighted version of
the STC+. The weighted STC is hard to compute, and our main contribution is an
efficient 2-approximation (resp. 3-approximation) streaming algorithm for the
weighted STC (resp. STC+) in temporal networks. As a technical contribution, we
introduce a fully dynamic -approximation for the minimum weighted vertex
cover problem in hypergraphs with edges of size , which is a crucial
component of our streaming algorithms. An empirical evaluation shows that the
weighted STC leads to solutions that better capture the a priori knowledge
given by the edge weights than the non-weighted STC. Moreover, we show that our
streaming algorithm efficiently approximates the weighted STC in real-world
large-scale social networks
An Edge-Based Decomposition Framework for Temporal Networks
No full textInternational audienceA temporal network is a dynamic graph where every edge is assigned an integer time label that indicates at which discrete time step the edge is available. We consider the problem of hierarchically decomposing the network and introduce an edge-based decomposition framework that unifies the core and truss decompositions for temporal networks while allowing us to consider the network's temporal dimension. Based on our new framework, we introduce the -core and -truss decompositions, which are generalizations of the classic -core and -truss decompositions for multigraphs. Moreover, we show how -cores and -trusses can be efficiently further decomposed to obtain spatially and temporally connected components. We evaluate the characteristics of our new decompositions and the efficiency of our algorithms. Moreover, we demonstrate how our -decompositions can be applied to analyze malicious content in a Twitter network to obtain insights that state-of-the-art baselines cannot obtain
- …
