共查询到20条相似文献,搜索用时 15 毫秒
1.
An Approximation Algorithm for the Minimum Co-Path Set Problem 总被引:1,自引:0,他引:1
We present an approximation algorithm for the problem of finding a minimum set of edges in a given graph G whose removal from G leaves a graph in which each connected component is a path. It achieves a ratio of
\frac 107\frac {10}{7}
and runs in O(n
1.5) time, where n is the number of vertices in the input graph. The previously best approximation algorithm for this problem achieves a ratio
of 2 and runs in O(n
2) time. 相似文献
2.
In Dijkstra (Commun ACM 17(11):643–644, 1974) introduced the notion of self-stabilizing algorithms and presented three such
algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib
Comput 1:5–6, 1986) a proof of its correctness was presented, but the question of determining its worst case complexity—that
is, providing an upper bound on the number of moves of this algorithm until it stabilizes—remained open. In this paper we
solve this question and prove an upper bound of
3\frac1318 n2 + O(n){3\frac{13}{18} n^2 + O(n)} for the complexity of this algorithm. We also show a lower bound of
1\frac56 n2 - O(n){1\frac{5}{6} n^2 - O(n)} for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis.
We also present a new-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of
\frac56 n2 + O(n){\frac{5}{6} n^2 + O(n)} for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing
systems, pp 17.1–17.13, 1995) presented a similar three-state algorithm, with an upper bound of
5\frac34n2+O(n){5\frac{3}{4}n^2+O(n)} and a lower bound of
\frac18n2-O(n){\frac{1}{8}n^2-O(n)} for its stabilization time. For this algorithm we prove an upper bound of
1\frac12n2 + O(n){1\frac{1}{2}n^2 + O(n)} and show a lower bound of n
2−O(n). As far as the worst case performance is considered, the algorithm in Beauquier and Debas (Proceedings of the second workshop
on self-stabilizing systems, pp 17.1–17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11):643–644, 1974) and
our algorithm is better than both. 相似文献
3.
Tahmineh? Keshavarzi Farideh?Sedaghat G.?Ali?Mansoori 《Microfluidics and nanofluidics》2010,8(1):97-104
The aim of our research is to develop a theory, which can predict the behavior of confined fluids in nanoslit pores. The nanoslit
pores studied in this work consist of two structureless and parallel walls in the xy plane located at z = 0 and z = H, in equilibrium with a bulk homogeneous fluid at the same temperature and at a given uniform bulk density. We have derived
the following general equation for prediction of the normal pressure tensor P
zz
of confined inhomogeneous fluids in nanoslit pores:
$ P_{zz} = kT\rho \left( {r_{1z} } \right)\left[ {1 + \frac{1}{kT}\frac{{\partial \phi_{\text{ext}} }}{{\partial r_{1z} }}{\text{d}}r_{1z} } \right] - \frac{1}{2}\int\limits_{v} {\varphi^{\prime}(\vec{r}_{12} )\rho^{(2)} \left( {\overset{\lower0.5em\hbox{$ P_{zz} = kT\rho \left( {r_{1z} } \right)\left[ {1 + \frac{1}{kT}\frac{{\partial \phi_{\text{ext}} }}{{\partial r_{1z} }}{\text{d}}r_{1z} } \right] - \frac{1}{2}\int\limits_{v} {\varphi^{\prime}(\vec{r}_{12} )\rho^{(2)} \left( {\overset{\lower0.5em\hbox{ 相似文献
4.
In this paper, we study two variants of the bin packing and covering problems called Maximum Resource Bin Packing (MRBP) and Lazy Bin Covering (LBC) problems, and present new approximation algorithms for them. For the offline MRBP problem, the previous best known approximation
ratio is
\frac65\frac{6}{5}
(=1.2) achieved by the classical First-Fit-Increasing (FFI) algorithm (Boyar et al. in Theor. Comput. Sci. 362(1–3):127–139, 2006). In this paper, we give a new FFI-type algorithm with an approximation ratio of
\frac8071\frac{80}{71}
(≈1.12676). For the offline LBC problem, it has been shown in Lin et al. (COCOON, pp. 340–349, 2006) that the classical First-Fit-Decreasing (FFD) algorithm achieves an approximation ratio of
\frac7160\frac{71}{60}
(≈1.18333). In this paper, we present a new FFD-type algorithm with an approximation ratio of
\frac1715\frac{17}{15}
(≈1.13333). Our algorithms are based on a pattern-based technique and a number of other observations. They run in near linear
time (i.e., O(nlog n)), and therefore are practical. 相似文献
5.
Roel Verstappen 《Journal of scientific computing》2011,49(1):94-110
Large eddy simulation (LES) seeks to predict the dynamics of spatially filtered turbulent flows. The very essence is that
the LES-solution contains only scales of size ≥Δ, where Δ denotes some user-chosen length scale. This property enables us
to perform a LES when it is not feasible to compute the full, turbulent solution of the Navier-Stokes equations. Therefore,
in case the large eddy simulation is based on an eddy viscosity model we determine the eddy viscosity such that any scales
of size <Δ are dynamically insignificant. In this paper, we address the following two questions: how much eddy diffusion is
needed to (a) balance the production of scales of size smaller than Δ; and (b) damp any disturbances having a scale of size
smaller than Δ initially. From this we deduce that the eddy viscosity ν
e
has to depend on the invariants
q = \frac12tr(S2)q = \frac{1}{2}\mathrm{tr}(S^{2}) and
r = -\frac13tr(S3)r= -\frac{1}{3}\mathrm{tr}(S^{3}) of the (filtered) strain rate tensor S. The simplest model is then given by
ne = \frac32(D/p)2 |r|/q\nu_{e} = \frac{3}{2}(\Delta/\pi)^{2} |r|/q. This model is successfully tested for a turbulent channel flow (Re
τ
=590). 相似文献
6.
We investigate the natural situation of the dissemination of information on various graph classes starting with a random set
of informed vertices called active. Initially active vertices are chosen independently with probability p, and at any stage in the process, a vertex becomes active if the majority of its neighbours are active, and thereafter never
changes its state. This process is a particular case of bootstrap percolation. We show that in any cubic graph, with high
probability, the information will not spread to all vertices in the graph if
p < \frac12p<\frac{1}{2}
. We give families of graphs in which information spreads to all vertices with high probability for relatively small values
of p. 相似文献
7.
We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph
G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with
each cycle and the vector space over
\mathbbF2\mathbb{F}_{2}
generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a
minimum cycle basis of G. 相似文献
8.
On Defining Integers And Proving Arithmetic Circuit Lower Bounds 总被引:1,自引:1,他引:0
Peter Bürgisser 《Computational Complexity》2009,18(1):81-103
9.
The aim of our research is to demonstrate the role of attractive intermolecular potential energy on normal pressure tensor
of confined molecular fluids inside nanoslit pores of two structureless purely repulsive parallel walls in xy plane at z = 0 and z = H, in equilibrium with a bulk homogeneous fluid at the same temperature and at a uniform density. To achieve this we have derived
the perturbation theory version of the normal pressure tensor of confined inhomogeneous fluids in nanoslit pores:
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号 |