共查询到20条相似文献,搜索用时 31 毫秒
1.
《国际计算机数学杂志》2012,89(3):295-304
A pushdown automaton is said to make a turn at a given instant if it changes at that instant from stack increasing to stack decreasing. Let \hbox{NPDA-TURN}(\,f(n)) and \hbox{DPDA-TURN}(\,f(n)) denote the classes of languages accepted by nondeterministic and deterministic pushdown automata respectively that make at most f v ( n ) turns for any input of length n . In this paper the following inclusions that express the space complexity of turn bounded pushdown automata are given: \hbox{DPDA-TURN}(\,f(n)) \subseteq {\bf DSPACE}(\log f(n)\log n) , and \hbox{NPDA-TURN}(\,f(n)) \subseteq {\bf NSPACE} (\log f(n)\log n) . In particular, it follows that finite-turn pushdown automata are logarithmic space bounded: \hbox{DPDA-TURN}(O(1))\subseteq {\bf DL} and \hbox{NPDA-TURN}(O(1))\subseteq {\bf NL} , from which two corollaries follow: one is that the class of metalinear context-free languages is complete for NL , and the other is that a more tight inclusion \hbox{NPDA-TURN}(\,f(n)) \subseteq {\bf DSPACE}(\log^2 f(n)\log n) cannot be derived unless {\bf DL}={\bf NL} , though \hbox{NPDA-TURN} (\,f(n)) \subseteq {\bf DSPACE}(\log^2 f(n)\log^2n) holds. 相似文献
2.
《Automatic Control, IEEE Transactions on》2009,54(6):1314-1318
3.
We present a new algorithm to compute motorcycle graphs. It runs in
time when n is the number of motorcycles. We give a new characterization of the straight skeleton of a nondegenerate polygon.
For a polygon with n vertices and h holes, we show that it yields a randomized algorithm that reduces the straight skeleton
computation to a motorcycle graph computation in expected
time. Combining these results, we can compute the straight skeleton of a nondegenerate polygon with h holes and with n
vertices, among which r are reflex vertices, in
expected time. In particular, we cancompute the straight skeleton of a nondegenerate polygon with n vertices in
expected time. 相似文献
4.
Anke Schneider Klaus-Peter Kröhn Anne Püschel 《Computing and Visualization in Science》2012,15(4):163-168
Beginning in 1995, the codes $\hbox {d}^{3}\hbox {f}$ (distributed density driven flow) and $\hbox {r}^{3}\hbox {t}$ (radionuclides, reaction, retardation, and transport) for modeling density-driven groundwater flow and nuclide transport using UG toolbox are developed in the framework of several joint projects. During this time, the codes were substantially extended as well as numerically improved, and the development is still ongoing. Now, $\hbox {d}^{3}\hbox {f}$ and $\hbox {r}^{3}\hbox {t}$ are no longer restricted to modeling of porous media, they also may be used for fractured rock. These are powerful tools that are able to handle salt and heat transport, salt concentrations up to saturation and complex hydrogeological structures with high permeability contrasts. 相似文献
5.
We consider a parameterized family{S_{alpha}, alpha in a}, a subset R^{infty} , of systems or sources having stochastic outputs{x_{n}} that are partially described by a statistic (e.g, correlation function)sigma_{alpha}(tau) . If we representalpha=(alpha_{1},alpha_{2}...,alpha_{n}...) , then by the system order M_{alpha} we mean the indexn of the last no nonzero term in the expansinn of α. Our objective is to generate a sequence{hat{M}_{n}(x_{1},... ,X_{n})} of estimates of theM_{alpha}^{0} that converge to it at least in probability. We provide conditions ensuring the existence of such a statistically consistent sequence of estimators, as wen as improved conditions yielding convergence in mean-square and with probability one. We establish existence by providing a method for constructing a family of consistent estimators of system order. We then apply our method to estimate the order of a scalar moving averages process and the order of a scalar autoregressive process. Our present results are primarily Of a theoretical nature, as we lack the efficiency and simulation studies desirable in support of a practical estimator of system order. 相似文献
6.
Lukasz Kowalik 《Algorithmica》2010,58(3):770-789
Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Grötzsch’s theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n 2) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is $\mathcal{O}(n\log n)Although deciding whether the vertices of a planar graph can be colored with three colors is NP-hard, the widely known Gr?tzsch’s
theorem states that every triangle-free planar graph is 3-colorable. We show the first o(n
2) algorithm for 3-coloring vertices of triangle-free planar graphs. The time complexity of the algorithm is
O(nlogn)\mathcal{O}(n\log n)
. 相似文献
7.
《国际计算机数学杂志》2012,89(5):665-670
This work is concerned with computing the solution of the following inverse problem: Finding u and 𝜌on D such that: $$\nabla \cdot (\rho \nabla u) = 0,\quad \hbox{on}\ D;$$ $$u = g,\quad \hbox{on}\ \partial D;\qquad \rho u_n = f,\quad \hbox{on}\ \partial D;$$ $$\rho (x_0, y_0) = \rho_0,\quad \hbox{for a given point}\ (x_0, y_0) \in D$$ where f and g are two given continuous functions defined on the boundary of D , and D is a given bounded region of R 2 . The solution is found using a development of the direct variational method. The two unknown functions are represented by linear combinations of certain classes of functions and using multiobjective optimization to minimize the two objective functionals F and H , where $$F = \vint \vint_D \rho (x,y) \nabla u\cdot \nabla u\,\hbox{d}x\,\hbox{d}y\quad \hbox{and}\quad H = \vint_{\partial D} (\rho u_n - f)^2 \hbox{d}s$$ A computer program is written and implemented and tested for data formed by numerical simulation. 相似文献
8.
Mariano Zelke 《Algorithmica》2012,62(1-2):1-20
We present an approximation algorithm to find a weighted matching of a graph in the one-pass semi-streaming model. The semi-streaming model forbids random access to the input graph and restricts the memory to ${\mathcal{O}}(n\cdot\operatorname{polylog}n)$ bits where n denotes the number of the vertices of the input graph. We obtain an approximation ratio of 5.58 while the previously best algorithm achieves a ratio of 5.82. 相似文献
9.
Thomas Sauerwald 《Algorithmica》2010,56(1):51-88
In this paper, we consider a popular randomized broadcasting algorithm called push-algorithm defined as follows. Initially,
one vertex of a graph G=(V,E) owns a piece of information which is spread iteratively to all other vertices: in each timestep t=1,2,… every informed vertex chooses a neighbor uniformly at random and informs it. The question is how many time steps are required until all
vertices become informed (with high probability).
For various graph classes, involved methods have been developed in order to show an upper bound of
O(logN+diam(G))\mathcal{O}(\log N+\mathop{\mathrm{diam}}(G))
on the runtime of the push-algorithm, where N is the number of vertices and
diam(G)\mathop{\mathrm{diam}}(G)
denotes the diameter of G. However, no asymptotically tight bound on the runtime based on the mixing time of random walks has been established. In
this work we fill this gap by deriving an upper bound of
O(Tmix+logN)\mathcal{O}(\mathsf {T}_{\mathop{\mathrm{mix}}}+\log N)
, where
Tmix\mathsf{T}_{\mathop{\mathrm{mix}}}
denotes the mixing time of a certain random walk on G. After that we prove upper bounds that are based on certain edge expansion properties of G. However, for hypercubes neither the bound based on the mixing time nor the bounds based on edge expansion properties are
tight. That is why we develop a general way to combine these two approaches by which we can deduce that the runtime of the
push-algorithm is Θ(log N) on every Hamming graph. 相似文献
10.
The no-three-in-line problem, introduced by Dudeney in 1917, asks for the maximum number of points in the n × n grid with
no three points collinear. Erdos proved that the answer is Θ(n). We consider the analogous problem in three dimensions, and
prove that the maximum number of points in the n × n × n grid with no three collinear is Θ(n2). This result is generalised by the notion of a 3D drawing of a graph. Here each vertex is represented by a distinct gridpoint
in
, such that the line-segment representing each edge does not intersect any vertex, except for its own endpoints. Note that
edges may cross. A 3D drawing of a complete graph Kn is nothing more than a set of n gridpoints with no three collinear. A slight generalisation of our first result is that the
minimum volume for a 3D drawing of Kn is Θ(n3/2). This compares favourably with Θ(n3) when edges are not allowed to cross. Generalising the construction for Kn, we prove that every k-colourable graph on n vertices has a 3D drawing with
volume, which is optimal for the k-partite Turan graph. 相似文献
11.
The unit ball random geometric graph
has as its vertices n points distributed independently and uniformly in the unit ball in
, with two vertices adjacent if and only if their ℓp-distance is at most λ. Like its cousin the Erdos-Renyi random graph, G has a connectivity threshold: an asymptotic value
for λ in terms of n, above which G is connected and below which G is disconnected. In the connected zone we determine upper
and lower bounds for the graph diameter of G. Specifically, almost always,
, where
is the ℓp-diameter of the unit ball B. We employ a combination of methods from probabilistic combinatorics and stochastic geometry. 相似文献
12.
Neural Computing and Applications - In graph theory, a vertex covering set $$V_\mathrm{C}$$ is a set of vertices such that each edge of the graph is incident to at least one of the vertices of the... 相似文献
13.
Given an undirected graph G with edge costs and a specified set of terminals, let the density of any subgraph be the ratio of its cost to the number of terminals it contains. If G is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of?G? We answer this question in the affirmative by giving an algorithm to pruneG and find such subgraphs of any desired size, incurring only a logarithmic factor increase in density (plus a small additive term). We apply our pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the k-2VC problem, we are given an undirected graph G with edge costs and an integer k; the goal is to find a minimum-cost 2-vertex-connected subgraph of G containing at least k vertices. In the Budget-2VC problem, we are given a graph G with edge costs, and a budget B; the goal is to find a 2-vertex-connected subgraph H of G with total edge cost at most B that maximizes the number of vertices in H. We describe an O(log?nlog?k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an $O(\frac{1}{\epsilon}\log^{2} n)$ approximation, while violating the budget by a factor of at most 2+ε. 相似文献
14.
The distance between at least two vertices becomes longer after the removal of a hinge vertex. Thus a faulty hinge vertex
will increase the overall communication cost in a network. Therefore, finding the set of all hinge vertices in a graph can
be used to identify critical nodes in a real network. An O(n log n) time algorithm has been proposed here to find all hinge vertices of a trapezoid graph with n vertices. 相似文献
15.
ten Caat M Maurits NM Roerdink JB 《IEEE transactions on visualization and computer graphics》2008,14(4):756-771
A typical data-driven visualization of electroencephalography (EEG) coherence is a graph layout, with vertices representing electrodes and edges representing significant coherences between electrode signals. A drawback of this layout is its visual clutter for multichannel EEG. To reduce clutter, we define a functional unit (FU) as a data-driven region of interest (ROI). An FU is a spatially connected set of electrodes recording pairwise significantly coherent signals, represented in the coherence graph by a spatially connected clique. Earlier we presented two methods to detect FUs: a maximal clique based (MCB) method (time complexity O(3n/3), with n being the number of vertices) and a more efficient watershed based (WB) method (time complexity O (n2 log n)). To reduce the potential over-segmentation of the WB method, we introduce here an improved WB (IWB) method (time complexity O(n2 log n)). The IWB method merges basins representing FUs during the segmentation if they are spatially connected and if their union is a clique. The WB and IWB methods are both up to a factor of 100,000 faster than the MCB method for a typical multichannel setting with 128 EEG channels, thus making interactive visualization of multichannel EEG coherence possible. Results show that considering the MCB method as the gold standard, the difference between IWB and MCB FU maps is smaller than between WB and MCB FU maps. We also introduce two novel group maps for data-driven group analysis as extensions of the IWB method. First, the group mean coherence map preserves dominant features from a collection of individual FU maps. Second, the group FU size map visualizes the average FU size per electrode across a collection of individual FU maps. Finally, we employ an extensive case study to evaluate the IWB FU map and the two new group maps for data-driven group analysis. Results, in accordance with the conventional findings, indicate differences in EEG coherence between younger and older adults. However, they also suggest that an initial selection of hypothesis-driven ROIs could be extended with additional data-driven ROIs. 相似文献
16.
We present approximation algorithms for the unsplittable flow problem (UFP) in undirected graphs. As is standard in this line
of research, we assume that the maximum
demand is at most the minimum capacity. We focus on the non-uniform capacity case in which the edge capacities can vary arbitrarily
over the graph. Our results are:
We obtain an
approximation ratio for UFP, where n is the number of vertices,
is the maximum degree, and
is the expansion of the graph. Furthermore, if we specialize to the case where all edges have the same capacity, our algorithm
gives an
approximation.
For certain strong constant-degree expanders considered by we obtain an
approximation for the uniform capacity case.
For UFP on the line and the ring, we give the first constant-factor approximation algorithms.
All of the above results improve if the maximum demand is bounded away from the minimum capacity. The above results either
improve upon or
are incomparable with previously known results for these problems. The main technique used for these results is randomized
rounding followed by greedy alteration, and is inspired by the use of this idea in recent work. 相似文献
17.
Bangham J.A. Chardaire P. Pye C.J. Ling P.D. 《IEEE transactions on pattern analysis and machine intelligence》1996,18(5):529-539
Sieves decompose one dimensional bounded functions (dm) m=1R that represent the information in a manner that is analogous to the pyramid of wavelets obtained by linear decomposition. Sieves based on sequences of increasing scale open-closings with flat structuring elements (M and N filters) map f to {d} and the recomposition, consisting of adding up all the granule functions, maps {d} to f. Experiments show that a more general property exists such that {dˆ} maps to fˆ and back to {dˆ} where the granule functions {dˆ} are obtained from {d} by applying any operator α consisting of changing the amplitudes of some granules, including zero, without changing their signs. In other words, the set of granule function vectors produced by the decomposition is closed under the operation α. An analytical proof of this property is presented. This property means that filters are useful in the context of feature recognition and, in addition, opens the way for an analysis of the noise resistance of sieves 相似文献
18.
《Journal of microelectromechanical systems》2008,17(6):1408-1417
19.
The increased availability of data describing biological interactions provides important clues on how complex chains of genes
and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures
such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures
are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find
an optimal path structure in
time and
space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number
of vertices in the path structure, and t is the maximum number of vertices (i.e., "width") at each level of the structure.
Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity
is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures,
we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures
with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity
by applying it to protein interaction networks in the DIP database. 相似文献
20.
Jung-Hyun Seo Jong-Seok Kim Hyung Jae Chang Hyeong-Ok Lee 《The Journal of supercomputing》2018,74(4):1636-1654
Network cost and fixed-degree characteristic for the graph are important factors to evaluate interconnection networks. In this paper, we propose hierarchical Petersen network (HPN) that is constructed in recursive and hierarchical structure based on a Petersen graph as a basic module. The degree of HPN(n) is 5, and HPN(n) has \(10^n\) nodes and \(2.5 \times 10^n\) edges. And we analyze its basic topological properties, routing algorithm, diameter, spanning tree, broadcasting algorithm and embedding. From the analysis, we prove that the diameter and network cost of HPN(n) are \(3\log _{10}N-1\) and \(15 \log _{10}N-1\), respectively, and it contains a spanning tree with the degree of 4. In addition, we propose link-disjoint one-to-all broadcasting algorithm and show that HPN(n) can be embedded into FP\(_k\) with expansion 1, dilation 2k and congestion 4. For most of the fixed-degree networks proposed, network cost and diameter require \(O(\sqrt{N})\) and the degree of the graph requires O(N). However, HPN(n) requires O(1) for the degree and \(O(\log _{10}N)\) for both diameter and network cost. As a result, the suggested interconnection network in this paper is superior to current fixed-degree and hierarchical networks in terms of network cost, diameter and the degree of the graph. 相似文献