共查询到20条相似文献,搜索用时 147 毫秒
1.
Optimally Cutting a Surface into a Disk 总被引:1,自引:0,他引:1
We consider the problem of cutting a subset of the edges of a polyhedral manifold
surface, possibly with boundary, to obtain a single topological disk, minimizing
either the total number of cut edges or their total length. We show that this
problem is NP-hard in general, even for manifolds without boundary and for punctured
spheres. We also describe an algorithm with running time n
O(g+k), where n is
the combinatorial complexity, g is the genus, and k is the number of boundary
components of the input surface. Finally, we describe a greedy algorithm that
outputs a O(log2
g)-approximation of the minimum cut graph in O(g
2
n log n)
time. 相似文献
2.
We study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O*(2(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O*(2mn/(m+n)). Both algorithms use polynomial space. 相似文献
3.
We present an O(n2) algorithm for finding a specified oriented path of order at least n in a tournament of order n. Using this algorithm, we present an O(n2) algorithm that finds a specified oriented path from a given vertex if one exists. 相似文献
4.
We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs Gn,p (above the connectivity threshold) and for random regular graphs Gr,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t* all components are of size O(log n). For Gn,p and Gr we give the value of t*, and the size of Γ(t). For Gr, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs Dn,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 相似文献
5.
We give a randomized algorithm using O(n7 log2 n) separation calls to approximate the volume of a convex body with a fixed relative error. The bound is O(n6 log4 n) for centrally symmpetric bodies and for polytopes with a polynomial number of facets, and O(n5 log4 n) for centrally symmetric polytopes with a polynomial number of facets. We also give an O(n6 log n) algorithm to sample a point from the uniform distribution over a convex body. Several tools are developed that may be interesting on their own. We extend results of Sinclair–Jerrum [43] and the authors [34] on the mixing rate of Markov chains from finite to arbitrary Markov chains. We also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. © 1993 John Wiley & Sons, Inc. 相似文献
6.
László Lovász 《Mathematical Programming》1999,86(3):443-461
It is shown that the “hit-and-run” algorithm for sampling from a convex body K (introduced by R.L. Smith) mixes in time O
*(n
2
R
2/r
2), where R and r are the radii of the inscribed and circumscribed balls of K. Thus after appropriate preprocessing, hit-and-run produces an approximately uniformly distributed sample point in time O
*(n
3), which matches the best known bound for other sampling algorithms. We show that the bound is best possible in terms of R,r and n.
Received January 26, 1998 / Revised version received October 26, 1998?Published online July 19, 1999 相似文献
7.
Jacek Blazewicz Marta Kasprzak Benjamin Leroy-Beaulieu Dominique de Werra 《Discrete Applied Mathematics》2008,156(13):2573-2580
This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothermic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718–729]. This paper presents a class of digraphs: the quasi-adjoint graphs. This class includes the ones used in the paper cited above. A polynomial recognition algorithm in O(n3), as well as a polynomial algorithm in O(n2+m2) for finding a Hamiltonian circuit in these graphs are given. Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a path with three vertices) are discussed. 相似文献
8.
We prove that, for any constant ɛ>0, the complexity of the vertical decomposition of a set ofn triangles in three-dimensional space isO(n
2+ɛ
+K), whereK is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is
shown to beO(n
2+ɛ
). These bounds are almost tight in the worst case.
We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs inO(n
2
logn+V logn) time, whereV is the complexity of the decomposition. The algorithm is reasonably simple (in particular, it tries to perform as much of
the computation in two-dimensional spaces as possible) and thus is a good candidate for efficient implementations.
The algorithm is extended to compute the vertical decomposition of arrangements ofn algebraic surface patches of constant maximum degree in three-dimensional space in timeO(nλ
q
(n) logn +V logn), whereV is the combinatorial complexity of the vertical decomposition, λ
q
(n) is a near-linear function related to Davenport-Schinzel sequences, andq is a constant that depends on the degree of the surface patches and their boundaries. We also present an algorithm with improved
running time for the case of triangles which is, however, more complicated than the first algorithm.
Mark de Berg was supported by the Dutch Organization for Scientific Research (N.W.O.), and by ESPRIT Basic Research Action
No. 7141 (project ALCOM II:Algorithms and Complexity). Leonidas Guibas was supported by NSF Grant CCR-9215219, by a grant from the Stanford SIMA Consortium, by NSF/ARPA Grant
IRI-9306544, and by grants from the Digital Equipment, Mitsubishi, and Toshiba Corporations. Dan Halperin was supported by
a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA
Grant IRI-9306544, and by NSF Grant CCR-9215219. A preliminary version of this paper appeared inProc. 10th ACM Symposium on Computational Geometry, 1994, pp. 1–10. 相似文献
9.
Mean-shift is an iterative procedure often used as a nonparametric clustering algorithm that defines clusters based on the modal regions of a density function. The algorithm is conceptually appealing and makes assumptions neither about the shape of the clusters nor about their number. However, with a complexity of O(n2) per iteration, it does not scale well to large datasets. We propose a novel algorithm which performs density-based clustering much quicker than mean shift, yet delivering virtually identical results. This algorithm combines subsampling and a stochastic approximation procedure to achieve a potential complexity of O(n) at each step. Its convergence is established. Its performances are evaluated using simulations and applications to image segmentation, where the algorithm was tens or hundreds of times faster than mean shift, yet causing negligible amounts of clustering errors. The algorithm can be combined with existing approaches to further accelerate clustering. 相似文献
10.
Colin Cooper Alan Frieze Kurt Mehlhorn Volker Priebe 《Random Structures and Algorithms》2000,16(1):33-46
We study the average‐case complexity of shortest‐paths problems in the vertex‐potential model. The vertex‐potential model is a family of probability distributions on complete directed graphs with arbitrary real edge lengths, but without negative cycles. We show that on a graph with n vertices and with respect to this model, the single‐source shortest‐paths problem can be solved in O(n2) expected time, and the all‐pairs shortest‐paths problem can be solved in O(n2 log n) expected time. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 33–46, 2000 相似文献
11.
Jesper Makholm Byskov Bolette Ammitzbll Madsen Bjarke Skjernaa 《Journal of Graph Theory》2005,48(2):127-132
We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105n/10 ≈ 1.5926n; such subgraphs show an upper bound of O(12n/4) = O(1.8613n) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005 相似文献
12.
We consider the problem of selecting a subset of p investments of maximum total return out of a set of n available investments with uncertain returns, where uncertainty is represented by interval estimates for the returns, and the minmax regret objective is used. We develop an algorithm that solves this problem in O(min{p,n–p}n) time. This improves the previously known complexity O(min{p,n–p}2n).This research has been supported by the Spanish Science and Technology Ministry and FEDER Grant No. BFM2002-04525-C02-02.Received: October 2002 / Accepted: September 2003 相似文献
13.
Pankaj K. Agarwal Cecilia M. Procopiuc 《Journal of Algorithms in Cognition, Informatics and Logic》2003,46(2):115-139
We consider the following two instances of the projective clustering problem: Given a set S of n points in
and an integer k>0, cover S by k slabs (respectively d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. Let w* be the smallest value so that S can be covered by k slabs (respectively d-cylinders), each of width (respectively diameter) at most w*. This paper contains three main results: (i) For d=2, we present a randomized algorithm that computes O(klogk) strips of width at most w* that cover S. Its expected running time is O(nk2log4n) if k2logkn; for larger values of k, the expected running time is O(n2/3k8/3log14/3n). (ii) For d=3, a cover of S by O(klogk) slabs of width at most w* can be computed in expected time O(n3/2k9/4polylog(n)). (iii) We compute a cover of
by O(dklogk) d-cylinders of diameter at most 8w* in expected time O(dnk3log4n). We also present a few extensions of this result. 相似文献
14.
M. Sharir 《Discrete and Computational Geometry》1994,12(1):327-345
We consider the problem of bounding the combinatorial complexity of the lower envelope ofn surfaces or surface patches ind-space (d≥3), all algebraic of constant degree, and bounded by algebraic surfaces of constant degree. We show that the complexity of
the lower envelope ofn such surface patches isO(n
d−1+∈), for any ∈>0; the constant of proportionality depends on ∈, ond, ons, the maximum number of intersections among anyd-tuple of the given surfaces, and on the shape and degree of the surface patches and of their boundaries. This is the first
nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity
of the envelope isO(n
d-2λ
q
(n)) for some constantq depending on the shape and degree of the surfaces (where λ
q
(n) is the maximum length of (n, q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with
expected running timeO(n
2+∈), and give several applications of the new bounds.
Work on this paper has been supported by NSF Grant CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation,
the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered
by the Israeli Academy of Sciences. 相似文献
15.
Approximation of an open polygonal curve with a minimum number of circular arcs and biarcs 总被引:1,自引:0,他引:1
We present an algorithm for approximating a given open polygonal curve with a minimum number of circular arcs. In computer-aided manufacturing environments, the paths of cutting tools are usually described with circular arcs and straight line segments. Greedy algorithms for approximating a polygonal curve with curves of higher order can be found in the literature. Without theoretical bounds it is difficult to say anything about the quality of these algorithms. We present an algorithm which finds a series of circular arcs that approximate the polygonal curve while remaining within a given tolerance region. This series contains the minimum number of arcs of any such series. Our algorithm takes O(n2logn) time for an original polygonal chain with n vertices. Using a similar approach, we design an algorithm with a runtime of O(n2logn), for computing a tangent-continuous approximation with the minimum number of biarcs, for a sequence of points with given tangent directions. 相似文献
16.
In this paper, we consider the problem of computing the region visible to a query point located in a given polygonal domain. The polygonal domain is specified by a simple polygon with m holes and a total of n vertices. We provide two bounds on the complexity of this problem. One approach constructs a data structure with space complexity O(n2) in time O(n2lgn) and yields a query time of O((1+min(m,|V(q)|))lg2n+m+|V(q)|). Here, V(q) represents the set of vertices of the visibility polygon of a query point q, and |E| denotes the number of edges in the visibility graph. The other approach provides a data structure with space complexity O(min(|E|,mn)+n) in time O(T+|E|+nlgn) with the query time of O(|V(q)|lgn+m). Here, T is the time to triangulate the given polygonal region (which is O(n+mlg1+m) for a small positive constant >0). In both of these approaches, O(m) additive factor in the query time is eliminated with an additional O((min(|E|,mn))2) space and an additional O(m(min(|E|,mn))2) preprocessing time. 相似文献
17.
The study of simple stochastic games (SSGs) was initiated by Condon for analyzing the computational power of randomized space-bounded alternating Turing machines. The game is played by two players, MAX and MIN, on a directed multigraph, and when the play terminates at a sink vertex s, MAX wins from MIN a payoff p(s)∈[0,1]. Condon proved that the problem SSG-VALUE—given a SSG, determine whether the expected payoff won by MAX is greater than 1/2 when both players use their optimal strategies—is in NP∩coNP. However, the exact complexity of this problem remains open, as it is not known whether the problem is in P or is hard for some natural complexity class. In this paper, we study the computational complexity of a strategy improvement algorithm by Hoffman and Karp for this problem. The Hoffman–Karp algorithm converges to optimal strategies of a given SSG, but no non-trivial bounds were previously known on its running time. We prove a bound of O(n2/n) on the convergence time of the Hoffman–Karp algorithm, and a bound of O(20.78n) on a randomized variant. These are the first non-trivial upper bounds on the convergence time of these strategy improvement algorithms. 相似文献
18.
A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)2) whenO(n
2.81/logn) processors are used. 相似文献
19.
We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2χχ2n(χ−2)/(χ−1)(log n)1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is
. All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)χ−1), due to Noga Alon (personal communication, September 1989). 相似文献
20.
Aronov Boris van Kreveld Marc van Oostrum René Varadarajan Kasturi 《Discrete and Computational Geometry》2003,30(3):357-372
Given an orientable genus-0 polyhedral surface defined by n
triangles, and a set of m point sites} on it, we would like
to identify its 1-center, i.e., the location on the surface that
minimizes the maximum distance to the sites. The distance is
measured as the length of the Euclidean shortest path along the
surface. To compute the 1-center, we compute the furthest-site
Voronoi diagram of the sites on the polyhedral surface. We show that
the diagram has maximum combinatorial complexity (m
n
2), and
present an algorithm that computes the diagram in O(m
n
2log mlog
n) expected time. The 1-center can then be identified in time
linear in the size of the diagram. 相似文献