A Directed Path Family is a family of subsets of some finite ground set whose members can be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph G such that each word in the language is the set of arcs of some path in G, is a polynomial-time solvable problem.
Directed line graph Hypergraph 2-colorability Recognition algorithms
Relative dispersion of tracers - i.e. very small, neutrally buoyant particles-, is particularly efficient in incompressible turbulent flows. Due to the non smooth behaviour of velocity differences in the inertial range, the separation distance between two trajectories, R(t)=X1(t)-X2(t) , grows as a power of time superdiffusively, R2(t)t3 , as first observed by L.F. Richardson [1]. This now well established result has no counterpart in the theory of heavy particle suspensions, namely finite-size particles with a mass density much larger that of the carrier fluid. The complete knowledge of particle properties of mixing in turbulent flows -yet an open problem-, is of great importance in cloud physics, or in estimating pollutant dispersion for hazardous safety purposes.
n this paper a numerical approach for binary fluid mixtures is proposed. A
lattice Boltzmann algorithm for the continuity and the Navier-Stokes equations
is coupled to a finite-difference scheme for the convection-diffusion equation.
A free-energy is used to derive the thermodynamic quantities related to the
equilibrium properties of the system. Spurious velocities are reduced by using
a general stencil scheme for discretizing spatial derivatives.
