Search results for "data structure"
showing 10 items of 441 documents
Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm
2020
In 1996, Bodlaender showed the celebrated result that an optimal tree decomposition of a graph of bounded treewidth can be found in linear time. The algorithm is based on an algorithm of Bodlaender and Kloks that computes an optimal tree decomposition given a non-optimal tree decomposition of bounded width. Both algorithms, in particular the second, are hardly accessible. We present the second algorithm in a much simpler way in this paper and refer to an extended version for the first. In our description of the second algorithm, we start by explaining how all tree decompositions of subtrees defined by the nodes of the given tree decomposition can be enumerated. We group tree decompositions …
$O(n^2 log n)$ Time On-line Construction of Two-Dimensional Suffix Trees
2007
The two-dimensional suffix tree of an n × n square matrix A is a compacted trie that represents all square submatrices of A [11]. For the off-line case, i.e., A is given in advance to the algorithm, it is known how to build it in optimal time, for any type of alphabet size [11], [18]. Motivated by applications in Image Compression [22], Giancarlo and Guaiana [14] considered the on-line version of the two-dimensional suffix tree and presented an O(n2 log2 n)-time algorithm, which we refer to as GG. That algorithm is a nontrivial generalization of Ukkonen’s on-line algorithm for standard suffix trees [23]. The main contribution in this paper is an O(logn) factor improvement in the time comple…
Distributed Leader Election and Computation of Local Identifiers for Programmable Matter
2019
International audience; The context of this paper is programmable matter, which consists of a set of computational elements, called particles, in an infinite graph. The considered infinite graphs are the square, triangular and king grids. Each particle occupies one vertex, can communicate with the adjacent particles, has the same clockwise direction and knows the local positions of neighborhood particles. Under these assumptions, we describe a new leader election algorithm affecting a variable to the particles, called the k-local identifier, in such a way that particles at close distance have each a different k-local identifier. For all the presented algorithms, the particles only need a O(…
Decremental 2- and 3-connectivity on planar graphs
1996
We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total ofO(n logn) time under any sequence of at mostO(n) deletions. This givesO(logn) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total ofO(n log2n) time. This givesO(log2n) amortized time per deletion. The space required by all our data structures isO(n). All our time bounds improve previous bounds.
Visual Tools in Virtual Reality: Complex Environment
1994
In this paper, we analyse an integrated system able to merge graphical and vision technique in order to improve virtual space environment. Virtual space is characterized by Dynamic Visual Icons and Virtual Reality for arising a hererogeneous environment. Essentially, we propose a fusion technique between visual icon and virtual space, where their integration is supported by Visual lcon Grammar (VIG) working on Dynamic lcon and Visual World. VIG allows to test the actions of the Dynamic Icon on the active Visual Word metaphor at the lime "t", and the different rage of transactions between user and VW(visual query, view and brows of under-world,... ). Moreover, user can define, modify and rem…
Lightweight LCP construction for next-generation sequencing datasets
2012
The advent of "next-generation" DNA sequencing (NGS) technologies has meant that collections of hundreds of millions of DNA sequences are now commonplace in bioinformatics. Knowing the longest common prefix array (LCP) of such a collection would facilitate the rapid computation of maximal exact matches, shortest unique substrings and shortest absent words. CPU-efficient algorithms for computing the LCP of a string have been described in the literature, but require the presence in RAM of large data structures. This prevents such methods from being feasible for NGS datasets. In this paper we propose the first lightweight method that simultaneously computes, via sequential scans, the LCP and B…
Toward a virtual reconstruction of an antique three-dimensional marble puzzle
2017
International audience; Abstract | Introduction | Related Work | Acquisition Setup, Proposed Prototype: Calibration and Visibility | Preprocessing of Scanned Three-Dimensional Fragment Data | Processing of Scanned Three-Dimensional Surface Data: Matching | Conclusion and Future Works | Appendices | Acknowledgments | ReferencesAbstract. The reconstruction of broken objects is an important field of research for many applications, such as art restoration, surgery, forensics, and solving puzzles. In archaeology, the reconstruction of broken artifacts is a very time-consuming task due to the handling of fractured objects, which are generally fragile. However, it can now be supported by three-dim…
Bords d'une surface médiane : Identifications et applications
2014
National audience; Un squelette d'une forme fermée est une structure mince, centrée dans cette forme, décrivant sa topologie et sa géométrie. Les squelettes permettent de développer des applications interactives en synthèse d'images~: l'utilisateur peut manipuler intuitivement des formes en modifiant leurs squelettes. Parmi toutes les formulations de squelettes, nous nous intéressons en particulier à la surface médiane. Ses éléments, nommés atomes, sont les sphères maximales intérieures à la forme décrite. Les positions des atomes sont organisées en courbes et surfaces, qui composent la structure squelettale. Cette structure peut être d'une grande aide pour manipuler une forme. Cependant, e…
WSN localization scheme based on Received Signal Strength Indicator (RSSI) for ZigBee Networks
2015
International audience; Wireless Sensor Networks (WSNs) have diverse application domains such as smart home, smart care, industrial, etc. We present a WSN system based on the ZigBee technology (IEEE 802.15.4) in Smart Home. In our paper we interest to ZigBee protocol is often used in medical Rehabilitation, which is a relatively new concept involving wireless transmission of data from the sensors attached to a patient to a distant monitoring station. There is no standardized topology managing the current networks, therefore, we will compare and evaluate the performance the mobility of nodes for star topologies in different scenarios to determine which is the most suitable in a typical hospi…
Detection and matching of curvilinear structures
2011
We propose an approach to curvilinear and wiry object detection and matching based on a new curvilinear region detector (CRD) and a shape context-like descriptor (COH). Standard methods for local patch detection and description are not directly applicable to wiry objects and curvilinear structures, such as roads, railroads and rivers in satellite and aerial images, vessels and veins in medical images, cables, poles and fences in urban scenes, stems and tree branches in natural images, since they assume the object is compact, i.e. that most elliptical patches around features cover only the object. However, wiry objects often have no flat parts and most neighborhoods include both foreground a…