Search results for " graph"
showing 10 items of 1277 documents
Deep Non-Line-of-Sight Reconstruction
2020
The recent years have seen a surge of interest in methods for imaging beyond the direct line of sight. The most prominent techniques rely on time-resolved optical impulse responses, obtained by illuminating a diffuse wall with an ultrashort light pulse and observing multi-bounce indirect reflections with an ultrafast time-resolved imager. Reconstruction of geometry from such data, however, is a complex non-linear inverse problem that comes with substantial computational demands. In this paper, we employ convolutional feed-forward networks for solving the reconstruction problem efficiently while maintaining good reconstruction quality. Specifically, we devise a tailored autoencoder architect…
Multi-GPU Accelerated Multi-Spin Monte Carlo Simulations of the 2D Ising Model
2010
A Modern Graphics Processing unit (GPU) is able to perform massively parallel scientific computations at low cost. We extend our implementation of the checkerboard algorithm for the two-dimensional Ising model [T. Preis et al., Journal of Chemical Physics 228 (2009) 4468–4477] in order to overcome the memory limitations of a single GPU which enables us to simulate significantly larger systems. Using multi-spin coding techniques, we are able to accelerate simulations on a single GPU by factors up to 35 compared to an optimized single Central Processor Unit (CPU) core implementation which employs multi-spin coding. By combining the Compute Unified Device Architecture (CUDA) with the Message P…
Some complexity and approximation results for coupled-tasks scheduling problem according to topology
2016
International audience; We consider the makespan minimization coupled-tasks problem in presence of compatibility constraints with a specified topology. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We study several problems in framework of classic complexity and approximation for which the compatibility graph is bipartite (star, chain,. . .). In such a context, we design some efficient polynomial-time approximation algorithms for an intractable scheduling problem according to some parameters.
Anti-powers in infinite words
2018
In combinatorics of words, a concatenation of $k$ consecutive equal blocks is called a power of order $k$. In this paper we take a different point of view and define an anti-power of order $k$ as a concatenation of $k$ consecutive pairwise distinct blocks of the same length. As a main result, we show that every infinite word contains powers of any order or anti-powers of any order. That is, the existence of powers or anti-powers is an unavoidable regularity. Indeed, we prove a stronger result, which relates the density of anti-powers to the existence of a factor that occurs with arbitrary exponent. As a consequence, we show that in every aperiodic uniformly recurrent word, anti-powers of ev…
REDUCTION OF CONSTRAINT SYSTEMS
1993
Geometric modeling by constraints leads to large systems of algebraic equations. This paper studies bipartite graphs underlaid by systems of equations. It shows how these graphs make possible to polynomially decompose these systems into well constrained, over-, and underconstrained subsystems. This paper also gives an efficient method to decompose well constrained systems into irreducible ones. These decompositions greatly speed up the resolution in case of reducible systems. They also allow debugging systems of constraints.
Online shortest paths with confidence intervals for routing in a time varying random network
2018
International audience; The increase in the world's population and rising standards of living is leading to an ever-increasing number of vehicles on the roads, and with it ever-increasing difficulties in traffic management. This traffic management in transport networks can be clearly optimized by using information and communication technologies referred as Intelligent Transport Systems (ITS). This management problem is usually reformulated as finding the shortest path in a time varying random graph. In this article, an online shortest path computation using stochastic gradient descent is proposed. This routing algorithm for ITS traffic management is based on the online Frank-Wolfe approach.…
On the family of $r$-regular graphs with Grundy number $r+1$
2014
International audience; The Grundy number of a graph $G$, denoted by $\Gamma(G)$, is the largest $k$ such that there exists a partition of $V(G)$, into $k$ independent sets $V_1,\ldots, V_k$ and every vertex of $V_i$ is adjacent to at least one vertex in $V_j$, for every $j < i$. The objects which are studied in this article are families of $r$-regular graphs such that $\Gamma(G) = r + 1$. Using the notion of independent module, a characterization of this family is given for $r=3$. Moreover, we determine classes of graphs in this family, in particular the class of $r$-regular graphs without induced $C_4$, for $r \le 4$. Furthermore, our propositions imply results on partial Grundy number.
Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
2017
We study quantum algorithms on search trees of unknown structure, in a model where the tree can be discovered by local exploration. That is, we are given the root of the tree and access to a black box which, given a vertex $v$, outputs the children of $v$. We construct a quantum algorithm which, given such access to a search tree of depth at most $n$, estimates the size of the tree $T$ within a factor of $1\pm \delta$ in $\tilde{O}(\sqrt{nT})$ steps. More generally, the same algorithm can be used to estimate size of directed acyclic graphs (DAGs) in a similar model. We then show two applications of this result: a) We show how to transform a classical backtracking search algorithm which exam…
Bootstrap validation of links of a minimum spanning tree
2018
We describe two different bootstrap methods applied to the detection of a minimum spanning tree obtained from a set of multivariate variables. We show that two different bootstrap procedures provide partly distinct information that can be highly informative about the investigated complex system. Our case study, based on the investigation of daily returns of a portfolio of stocks traded in the US equity markets, shows the degree of robustness and completeness of the information extracted with popular information filtering methods such as the minimum spanning tree and the planar maximally filtered graph. The first method performs a "row bootstrap" whereas the second method performs a "pair bo…
Community characterization of heterogeneous complex systems
2011
We introduce an analytical statistical method to characterize the communities detected in heterogeneous complex systems. By posing a suitable null hypothesis, our method makes use of the hypergeometric distribution to assess the probability that a given property is over-expressed in the elements of a community with respect to all the elements of the investigated set. We apply our method to two specific complex networks, namely a network of world movies and a network of physics preprints. The characterization of the elements and of the communities is done in terms of languages and countries for the movie network and of journals and subject categories for papers. We find that our method is ab…