Efficient algorithms for domination and Hamilton circuit problems on permutation graphs

The domination and Hamilton circuit problems are of interest both in algorithm design and complexity theory. The domination problem has applications in facility location and the Hamilton circuit problem has applications in routing problems in communications and operations research.The problem of deciding if G has a dominating set of cardinality at most k, and the problem of determining if G has a Hamilton circuit are NP-Complete. Polynomial time algorithms are, however, available for a large number of restricted classes. A motivation for the study of these algorithms is that they not only give insight into the characterization of these classes but also require a variety of algorithmic techniques and data structures. So the search for efficient algorithms, for these problems in many classes still continues.A class of perfect graphs which is practically important and mathematically interesting is the class of permutation graphs. The domination problem is polynomial time solvable on permutation graphs. Algorithms that are already available are of time complexity O(n2) or more, and space complexity O(n2) on these graphs. The Hamilton circuit problem is open for this class.We present a simple O(n) time and O(n) space algorithm for the domination problem on permutation graphs. Unlike the existing algorithms, we use the concept of geometric representation of permutation graphs. Further, exploiting this geometric notion, we develop an O(n2) time and O(n) space algorithm for the Hamilton circuit problem.

Algorithmic aspects of k-tuple total domination in graphs

For a fixed positive integer k, a k-tuple total dominating set of a graph G = (V. E) is a subset T D-k of V such that every vertex in V is adjacent to at least k vertices of T Dk. In minimum k-tuple total dominating set problem (MIN k-TUPLE TOTAL DOM SET), it is required to find a k-tuple total dominating set of minimum cardinality and DECIDE MIN k-TUPLE TOTAL DOM SET is the decision version of MIN k-TUPLE TOTAL DOM SET problem. In this paper, we show that DECIDE MIN k-TUPLE TOTAL DOM SET is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that MIN k-TUPLE TOTAL DOM SET can be solved in polynomial time. We also propose some hardness results and approximation algorithms for MIN k-TUPLE TOTAL DOM SET problem. (c) 2012 Elsevier B.V. All rights reserved.

Complexity of distance paired-domination problem in graphs

Suppose G = (V, E) is a simple graph and k is a fixed positive integer. A subset D subset of V is a distance k-dominating set of G if for every u is an element of V. there exists a vertex v is an element of D such that d(G)(u, v) <= k, where d(G)(u, v) is the distance between u and v in G. A set D subset of V is a distance k-paired-dominating set of G if D is a distance k-dominating set and the induced subgraph GD] contains a perfect matching. Given a graph G = (V, E) and a fixed integer k > 0, the MIN DISTANCE k-PAIRED-DOM SET problem is to find a minimum cardinality distance k-paired-dominating set of G. In this paper, we show that the decision version of MIN DISTANCE k-PAIRED-DOM SET iS NP-complete for undirected path graphs. This strengthens the complexity of decision version Of MIN DISTANCE k-PAIRED-DOM SET problem in chordal graphs. We show that for a given graph G, unless NP subset of DTIME (n(0)((log) (log) (n)) MIN DISTANCE k-PAIRED-Dom SET problem cannot be approximated within a factor of (1 -epsilon ) In n for any epsilon > 0, where n is the number of vertices in G. We also show that MIN DISTANCE k-PAIRED-DOM SET problem is APX-complete for graphs with degree bounded by 3. On the positive side, we present a linear time algorithm to compute the minimum cardinality of a distance k-paired-dominating set of a strongly chordal graph G if a strong elimination ordering of G is provided. We show that for a given graph G, MIN DISTANCE k-PAIRED-DOM SET problem can be approximated with an approximation factor of 1 + In 2 + k . In(Delta(G)), where Delta(G) denotes the maximum degree of G. (C) 2012 Elsevier B.V All rights reserved.

Relaminarization in highly accelerated turbulent boundary layers

The mean flow development in an initially turbulent boundary layer subjected to a large favourable pressure gradient beginning at a point x0 is examined through analyses expected a priori to be valid on either side of relaminarization. The ‘quasi-laminar’ flow in the later stages of reversion, where the Reynolds stresses have by definition no significant effect on the mean flow, is described by an asymptotic theory constructed for large values of a pressure-gradient parameter Λ, scaled on a characteristic Reynolds stress gradient. The limiting flow consists of an inner laminar boundary layer and a matching inviscid (but rotational) outer layer. There is consequently no entrainment to lowest order in Λ−1, and the boundary layer thins down to conserve outer vorticity. In fact, the predictions of the theory for the common measures of boundary-layer thickness are in excellent agreement with experimental results, almost all the way from x0. On the other hand the development of wall parameters like the skin friction suggests the presence of a short bubble-shaped reverse-transitional region on the wall, where neither turbulent nor quasi-laminar calculations are valid. The random velocity fluctuations inherited from the original turbulence decay with distance, in the inner layer, according to inverse-power laws characteristic of quasi-steady perturbations on a laminar flow. In the outer layer, there is evidence that the dominant physical mechanism is a rapid distortion of the turbulence, with viscous and inertia forces playing a secondary role. All the observations available suggest that final retransition to turbulence quickly follows the onset of instability in the inner layer.It is concluded that reversion in highly accelerated flows is essentially due to domination of pressure forces over the slowly responding Reynolds stresses in an originally turbulent flow, accompanied by the generation of a new laminar boundary layer stabilized by the favourable pressure gradient.

Rainbow connection number and connected dominating sets

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree delta, the rainbow connection number is upper bounded by 3n/(delta + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432437), improving the previously best known bound of 20n/delta (J Graph Theory 63 (2010), 185191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3n/(delta + 1) - 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree d. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc(G), is upper bounded by Gc(G) + 2, where Gc(G) is the connected domination number of G. Bounds of the form diameter(G)?rc(G)?diameter(G) + c, 1?c?4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree delta at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G)?3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds.

Nanoparticle agglomeration in an evaporating levitated droplet for different acoustic amplitudes

Radiatively heated levitated functional droplets with nanosilica suspensions exhibit three distinct stages namely pure evaporation, agglomeration, and finally structure formation. The temporal history of the droplet surface temperature shows two inflection points. One inflection point corresponds to a local maximum and demarcates the end of transient heating of the droplet and domination of vaporization. The second inflection point is a local minimum and indicates slowing down of the evaporation rate due to surface accumulation of nanoparticles. Morphology and final precipitation structures of levitated droplets are due to competing mechanisms of particle agglomeration, evaporation, and shape deformation. In this work, we provide a detailed analysis for each process and propose two important timescales for evaporation and agglomeration that determine the final diameter of the structure formed. It is seen that both agglomeration and evaporation timescales are similar functions of acoustic amplitude (sound pressure level), droplet size, viscosity, and density. However, we show that while the agglomeration timescale decreases with initial particle concentration, the evaporation timescale shows the opposite trend. The final normalized diameter can be shown to be dependent solely on the ratio of agglomeration to evaporation timescales for all concentrations and acoustic amplitudes. The structures also exhibit various aspect ratios (bowls, rings, spheroids) which depend on the ratio of the deformation timescale (t(def)) and the agglomeration timescale (t(g)). For t(def) < t(g), a sharp peak in aspect ratio is seen at low concentrations of nanosilica which separates high aspect ratio structures like rings from the low aspect ratio structures like bowls and spheroids. (C) 2013 American Institute of Physics. http://dx.doi.org/10.1063/1.4775791]