157 research outputs found
On the use of simulated experiments in designing tests for material characterization from full-field measurements
No full textThe present paper deals with the use of simulated experiments to improve the design of an actual mechanical test. The analysis focused on the identification of the orthotropic properties of composites using the unnotched Iosipescu test and a full-field optical technique, the grid method. The experimental test was reproduced numerically by finite element analysis and the recording of deformed grey level images by a CCD camera was simulated trying to take into account the most significant parameters that can play a role during an actual test, e.g. the noise, the failure of the specimen, the size of the grid printed on the surface, etc. The grid method then was applied to the generated synthetic images in order to extract the displacement and strain fields and the Virtual Fields Method was finally used to identify the material properties and a cost function was devised to evaluate the error in the identification. The developed procedure was used to study different features of the test such as the aspect ratio and the fibre orientation of the specimen, the use of smoothing functions in the strain reconstruction from noisy data, the influence of missing data on the identification. Four different composite materials were considered and, for each of them, a set of optimized design variables was found by minimization of the cost function
(Sub)linear Kernels for Edge Modification Problems Towards Structured Graph Classes
No full textIn a (parameterized) graph edge modification problem, we are given a graph G, an integer k and a (usually well-structured) class of graphs , and ask whether it is possible to transform G into a graph G' ∈ by adding and/or removing at most k edges. Parameterized graph edge modification problems received considerable attention in the last decades.
In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if this problem admits a 2k kernel [Cao and Chen, 2012], this kernel does not reduce the size of most instances. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graphs are very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size O(k/log k).
We also obtain small kernels for several other edge modification problems. We prove that Split Addition (and the equivalent Split Deletion) admits a linear kernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al., 2015]. We complement this result by proving that Trivially Perfect Addition admits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under ETH
PACE Challenge 2021: heuristique pour le cluster editing problem
No full textInternational audienceLe challenge PACE (https://pacechallenge.org/about/) est un challenge annuel organisé depuis 2015 ayant pour but d'aider au développement pratique d'algorithmes de résolution de problèmes complexes. Le challenge PACE 2021 était consacré à la résolution du Cluster Editing Problem. Nous allons présenter ici muSolver, un solveur développé par par Gabriel Bathie, Valentin Bartier, Nicolas Bousquet, Marc Heinrich, Théo Pierron et Ulysse Prieto qui s'est classé 3ème dans la partie heuristique du challenge 2021
PACE Challenge 2021: heuristique pour le cluster editing problem
No full textInternational audienceLe challenge PACE (https://pacechallenge.org/about/) est un challenge annuel organisé depuis 2015 ayant pour but d'aider au développement pratique d'algorithmes de résolution de problèmes complexes. Le challenge PACE 2021 était consacré à la résolution du Cluster Editing Problem. Nous allons présenter ici muSolver, un solveur développé par par Gabriel Bathie, Valentin Bartier, Nicolas Bousquet, Marc Heinrich, Théo Pierron et Ulysse Prieto qui s'est classé 3ème dans la partie heuristique du challenge 2021
PACE Challenge 2021: heuristique pour le cluster editing problem
No full textInternational audienceLe challenge PACE (https://pacechallenge.org/about/) est un challenge annuel organisé depuis 2015 ayant pour but d'aider au développement pratique d'algorithmes de résolution de problèmes complexes. Le challenge PACE 2021 était consacré à la résolution du Cluster Editing Problem. Nous allons présenter ici muSolver, un solveur développé par par Gabriel Bathie, Valentin Bartier, Nicolas Bousquet, Marc Heinrich, Théo Pierron et Ulysse Prieto qui s'est classé 3ème dans la partie heuristique du challenge 2021
Reconfiguration of Plane Trees in Convex Geometric Graphs
No full textA non-crossing spanning tree of a set of points in the plane is a spanning tree whose edges pairwise do not cross. Avis and Fukuda in 1996 proved that there always exists a flip sequence of length at most 2n-4 between any pair of non-crossing spanning trees (where n denotes the number of points). Hernando et al. proved that the length of a minimal flip sequence can be of length at least (3/2) n. Two recent results of Aichholzer et al. and Bousquet et al. improved the Avis and Fukuda upper bound by proving that there always exists a flip sequence of length respectively at most 2n-log n and 2n-√n when the points are in convex position.
We pursue the investigation of the convex case by improving the upper bound by a linear factor for the first time in 30 years. We prove that there always exists a flip sequence between any pair of non-crossing spanning trees T₁,T₂ of length at most c n where c ≈ 1.95. Our result is actually stronger since we prove that, for any two trees T₁,T₂, there exists a flip sequence from T₁ to T₂ of length at most c |T₁ ⧵ T₂|.
We also improve the best lower bound in terms of the symmetric difference by proving that there exists a pair of trees T₁,T₂ such that a minimal flip sequence has length (5/3) |T₁ ⧵ T₂|, improving the lower bound of Hernando et al. by considering the symmetric difference instead of the number of vertices.
We generalize this lower bound construction to non-crossing flips (where we close the gap between upper and lower bounds) and rotations
Lettres Sur Divers Points De Controverse Contenant les Principaux Motifs qui ont déterminé Son Altesse Serenissime Monseigneur Le Prince Frederic, Comte Palatin du Rhin, Duc de Baviere, ... A se reünir à la Sainte Eglise Catholique Apostolique & Romaine
No full text[Verf.: François Seedorff, de la Compagnie de Jesus ...]SommervogelVerf. ermittelt in: Bd. 2 auf S. 501Vorlageform des Erscheinungsvermerks: A Manhheim De l'Imprimerie Electorale Chéz Nicolas Pierron. M DCC XLIX.Erschienen: Bd. 1 -
Formal Definition of Disambiguation with Attribute Grammars
No full textThe current problem of the disambiguation in Transformers with attribute grammars is that no-one has a proof that allows certification of this approach. The current use of attribute grammars for the disambiguation of C and a part of C++ lets us think that this method is correct. In order to remove any doubt, a definition and a formalization of our approach are necessary. This work is split in two. The first part relates to the proof of the validity of the approach used in Transformers. The second part is devoted to the correction and the Re-development of the existing tools in order to correspond to the definite model
MicroRNA and gene co-expression networks characterize biological and clinical behavior of rhabdomyosarcomas
No full textAbstractRhabdomyosarcomas (RMS) in children and adolescents are heterogeneous sarcomas broadly defined by skeletal muscle features and the presence/absence of PAX3/7-FOXO1 fusion genes. MicroRNAs are small non-coding RNAs that regulate gene expression in a cell context specific manner. Sequencing analyses of microRNAs in 64 RMS revealed expression patterns separating skeletal muscle, fusion gene positive and negative RMS. Integration with parallel gene expression data assigned biological functions to 12 co-expression networks/modules that reassuringly included myogenic roles strongly correlated with microRNAs known in myogenesis and RMS development. Modules also correlated with clinical outcome and fusion status. Regulation of microRNAs by the fusion protein was demonstrated after PAX3-FOXO1 reduction, exemplified by miR-9-5p. MiR-9-5p levels correlated with poor outcome, even within fusion gene positive RMS, and were higher in metastatic versus non-metastatic disease. MiR-9-5p reduction inhibited RMS cell migration. Our findings reveal microRNAs in a regulatory framework of biological and clinical significance in RMS
How Local Constraints Influence Network Diameter and Applications to LCL Generalizations
No full textIn this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees as a function of the number of nodes, as listed below. These results have important consequences on the landscape of locally checkable labelings (LCL) on unbounded degree graphs, a case in which our lack of knowledge is in striking contrast with that of bounded degree graphs, that has been intensively studied recently.
First, we show that the diameter of a tree can be controlled very precisely by a local checker (that is, a distributed decision algorithm that accepts a graph iff all nodes accept locally), granted that its checkability radius is at least 2 (and that the target diameter is not too close to n). As a corollary, we prove that the gaps in the landscape of LCLs (in bounded-degree graphs) basically disappear in unbounded degree graphs.
Second, we prove that for checkers at distance 1, the maximum diameter can only be trivial (constant or linear), while the minimum diameter can in addition be Θ(log n) and Θ(n^(1/k)) for k ∈ ℕ. These functions interestingly coincide with the known regimes for LCLs.
Third, we explore computational restrictions of local checkers. In particular, we introduce a class of checkers, that we call degree-myopic, that cannot distinguish perfectly the degrees of their neighbors. With these checkers, we show that the maximum diameter can only be O(1), Θ(√n), Θ((log n)/(log log n)), Θ(log n), or Ω(n). Since gaps do appear in the maximum diameter, one can hope that an interesting LCL landscape exists for restricted local checkers.
In addition to the LCL motivation, we hope that our distributed lenses can help give a new point of view on how global structures, such as living beings, can be maintained by local phenomena; understanding the trade-off between the power of the checking and the possible resulting shapes
- …
