Search results for "COMPUTATION"

Almost disjoint spanning trees

2016

International audience; In this extended abstract, we only consider connected graphs. Let k ≥ 2 be an integer and T 1 ,. .. , T k be spanning trees in a graph G. A vertex is said to be an inner vertex in a tree T if it has degree at least 2 in T. We denote by I(T) the set of inner vertices of tree T. The spanning trees T 1 ,. .. , T k are completely independent spanning trees if any vertex from G is an inner vertex in at most one tree among T 1 ,. .. , T k and the trees T 1 ,. .. , T k are pairwise edge-disjoint. Completely independent spanning trees were introduced by Hasunuma [4] and then have been studied on different classes of graphs, such as underlying graphs of line graphs [4], maxim…

Recherche d'arbres couvrants complètement indépendants dans des graphes réguliers

2014

International audience; Nous étudions l'existence de $r$ arbres couvrants complètement indépendants dans des graphes $2r$-réguliers et $2r$-connexes, et énonçons des conditions nécessaires à leur existence. Nous déterminons le nombre maximum d'arbres dans les produits cartésiens d'une clique et d'un cycle. Nous montrons que ce nombre n'est pas toujours $r$.

Scheduling stretched coupled-tasks with compatibilities constraints : model, complexity and approximation results for some class of graphs

2014

We tackle the makespan minimization coupled-tasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, {\it i.e.}coupled-tasks having the same sub-tasks execution time and idle time duration. We study severals problems in frame works of classic complexity and approximation for which the compatibility graph $G_c$ is bipartite (star, chain, $\ldots$) In such context, we design some efficient polynomial-time approximation algorithms according to difference parameters of the scheduling problem. When $G_c$ is a $k$-stage bipartite graph, we propose, among other, a $\frac{7}{6}$-approximation algorithm when $k=1$, and a $\frac{13}{9}$-approximation…

Résolution des contraintes géométriques

1994

National audience; La modélisation par contraintes définit les objets géométriques (typiquement, en 2D, les points, droites, cercles, coniques, etc) par les contraintes qu'ils doivent vérifier (distances, angles, tangences, incidences, etc. entre paires d'objets). L'exposé tente de faire le point sur les diverses méthodes proposées à ce jour pour la résolution des contraintes, en 2D ou en 3D. Les méthodes algébriques transforment les contraintes en un système d'équations, et recourent ensuite à des méthodes numériques (relaxation, Newton-Raphson) [4] ou symboliques (bases de Grobner, méthode de Wu et Ritt) [5,3]. Les méthodes géométriques décomposent le système de contraintes en problèmes g…

Analysis of geometrical features of 3D model based on the surface curvature of a set of point cloud

2021

Modélisation géométrique de formes fractales pour la CAO

2020

International audience

Outils sémantiques pour diminuer l'entropie dans les réseaux socionumériques

2013

L'usage de plus en plus développé des réseaux socionumériques (RSN) actuels a permis d'accroître les interactions des utilisateurs en ligne, et dès lors il devient plus difficile d'appliquer les méthodes traditionnelles d'analyse des RSN pour capter les usages des internautes. Dans ce chapitre, nous présentons la vision du Web social sémantique, qui intègre la dimension sociale dans l'approche classique du Web sémantique.

Propose Semantic Formalization for 3D Reconstruction of Architectural

2010

International audience; Archi3D project is a successful practice well proved by engineering practices. In this paper, we propose to reconstruct semantics for the purpose of reconstruct 3D architecture in Archi3D fundamentally. The formalization approach starts from several hypotheses on semantics which include: there is a core mechanism of semantics which is not limited to conceptual expression level; and a complete expression of semantics necessaries the ―implicitexplicit‖ transition of human side knowledge, etc. The necessity and feasibility concerning applying the proposed method and technology to the practice of Archi3D is discussed systemically by way of semantics revelations on some …

Query-preserving watermarking of relational databases and XML documents

2011

Watermarking allows robust and unobtrusive insertion of information in a digital document. During the last few years, techniques have been proposed for watermarking relational databases or Xml documents, where information insertion must preserve a specific measure on data (for example the mean and variance of numerical attributes). In this article we investigate the problem of watermarking databases or Xml while preserving a set of parametric queries in a specified language, up to an acceptable distortion. We first show that unrestricted databases can not be watermarked while preserving trivial parametric queries. We then exhibit query languages and classes of structures that allow guarante…

Presentations of constrained systems with unconstrained positions

2005

International audience; We give a polynomial-time construction of the set of sequences that satisfy a finite-memory constraint defined by a finite list of forbidden blocks, with a specified set of bit positions unconstrained. Such a construction can be used to build modulation/error-correction codes (ECC codes) like the ones defined by the Immink-Wijngaarden scheme in which certain bit positions are reserved for ECC parity. We give a lineartime construction of a finite-state presentation of a constrained system defined by a periodic list of forbidden blocks. These systems, called periodic-finite-type systems, were introduced by Moision and Siegel. Finally, we present a linear-time algorithm for con…