共查询到20条相似文献,搜索用时 0 毫秒
1.
Marc van Kreveld Joseph S. B. Mitchell Peter Rousseeuw Micha Sharir Jack Snoeyink Bettina Speckmann 《Discrete and Computational Geometry》2008,39(4):656-677
We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n
d
) time and O(n
d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2
n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric
and algorithmic results.
A preliminary version of this paper appeared in the proceedings of the 15th Annual ACM Symposium on Computational Geometry
(1999)
M. van Kreveld partially funded by the Netherlands Organization for Scientific Research (NWO) under FOCUS/BRICKS grant number
642.065.503.
J.S.B. Mitchell’s research largely conducted while the author was a Fulbright Research Scholar at Tel Aviv University. The
author is partially supported by NSF (CCR-9504192, CCR-9732220), Boeing, Bridgeport Machines, Sandia, Seagull Technology,
and Sun Microsystems.
M. Sharir supported by NSF Grants CCR-97-32101 and CCR-94-24398, 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 ESPRIT IV LTR project No. 21957
(CGAL), and by the Hermann Minkowski—MINERVA Center for Geometry at Tel Aviv University.
J. Snoeyink supported in part by grants from NSERC, the Killam Foundation, and CIES while at the University of British Columbia. 相似文献
2.
《Journal of Complexity》1994,10(2):199-215
We consider two hybrid algorithms for finding an ϵ-approximation of a root of a convex real function that is twice differentiable and satisfies a certain growth condition on the intervial [0, R]. The first algorithm combines a binary search procedure with Newton′s method. The binary search produces an interval contained in the region of quadratic convergence of Newton′s method. The computational cost of the binary search, as well as the computational cost of Newton′s method, is of order O(log log(R/ϵ)). The second algorithm combines a binary search with the secant method in a similar fashion. This results in a lower overall computational cost when the cost of evaluating the derivative is more than .44042 of the cost of evaluating the function. Our results generalize same recent results of Ye. 相似文献
3.
Jørgen Bang‐Jensen Tilde My Christiansen Alessandro Maddaloni 《Journal of Graph Theory》2017,85(2):545-567
The k‐linkage problem is as follows: given a digraph and a collection of k terminal pairs such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths such that is from to for . A digraph is k‐linked if it has a k‐linkage for every choice of 2k distinct vertices and every choice of k pairs as above. The k‐linkage problem is NP‐complete already for [11] and there exists no function such that every ‐strong digraph has a k‐linkage for every choice of 2k distinct vertices of D [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the k‐linkage problem for any fixed k in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the k‐linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi‐transitive digraphs and directed cographs. We also prove that the necessary condition of being ‐strong is also sufficient for round‐decomposable digraphs to be k‐linked, obtaining thus a best possible bound that improves a previous one of . Finally we settle a conjecture from [3] by proving that every 5‐strong locally semicomplete digraph is 2‐linked. This bound is also best possible (already for tournaments) [1]. 相似文献
4.
Fatos Xhafa Enrique Alba Bernabé Dorronsoro Bernat Duran 《Journal of Mathematical Modelling and Algorithms》2008,7(2):217-236
Computational grids are an important emerging paradigm for large-scale distributed computing. As grid systems become more
wide-spread, techniques for efficiently exploiting the large amount of grid computing resources become increasingly indispensable.
A key aspect in order to benefit from these resources is the scheduling of jobs to grid resources. Due to the complex nature
of grid systems, the design of efficient grid schedulers becomes challenging since such schedulers have to be able to optimize
many conflicting criteria in very short periods of time. This problem has been tackled in the literature by several different
metaheuristics, and our main focus in this work is to develop a new highly competitive technique with respect to the existing
ones. For that, we exploit the capabilities of cellular memetic algorithms (cMAs), a kind of memetic algorithm with structured
population, for obtaining efficient batch schedulers for grid systems, and the obtained results will be compared versus the
state of the art. A careful design of the cMA methods and operators for the problem yielded to an efficient and robust implementation.
Our experimental study, based on a known static benchmark for the problem, shows that this heuristic approach is able to deliver
very high quality planning of jobs to grid nodes and thus it can be used to design efficient dynamic schedulers for real grid
systems. Such dynamic schedulers can be obtained by running the cMA-based scheduler in batch mode for a very short time to
schedule jobs arriving in the system since the last activation of the cMA scheduler.
This work has been partially funded by the Spanish MEC and FEDER under contract TIN2005-08818-C04-01 (the OPLINK project:
). 相似文献
5.
Chartrand and Pippert proved that a connected, locally k-connected graph is (k + 1)-connected. We investigate the lengths of k + 1 disjoint paths between two vertices in locally k-connected graphs with respect to several graph parameters, e.g. the k-diameter of a graph. We also give a generalization of the mentioned result.
This research was partly done on a visit to the Institute of Systems Science of Academia Sinica (Beijing, China) under the
project ME 418 of the Czech Ministery of Education. These authors are partly supported by the project LN00A056 of the Czech
Ministery of Education. 相似文献
6.
Ye Chen Zhi-Hong Chen Hong-Jian Lai Ping Li Erling Wei 《Graphs and Combinatorics》2013,29(6):1721-1731
Spanning connectivity of graphs has been intensively investigated in the study of interconnection networks (Hsu and Lin, Graph Theory and Interconnection Networks, 2009). For a graph G and an integer s > 0 and for ${u, v \in V(G)}$ with u ≠ v, an (s; u, v)-path-system of G is a subgraph H consisting of s internally disjoint (u,v)-paths. A graph G is spanning s-connected if for any ${u, v \in V(G)}$ with u ≠ v, G has a spanning (s; u, v)-path-system. The spanning connectivity κ*(G) of a graph G is the largest integer s such that G has a spanning (k; u, v)-path-system, for any integer k with 1 ≤ k ≤ s, and for any ${u, v \in V(G)}$ with u ≠ v. An edge counter-part of κ*(G), defined as the supereulerian width of a graph G, has been investigated in Chen et al. (Supereulerian graphs with width s and s-collapsible graphs, 2012). In Catlin and Lai (Graph Theory, Combinatorics, and Applications, vol. 1, pp. 207–222, 1991) proved that if a graph G has 2 edge-disjoint spanning trees, and if L(G) is the line graph of G, then κ*(L(G)) ≥ 2 if and only if κ(L(G)) ≥ 3. In this paper, we extend this result and prove that for any integer k ≥ 2, if G 0, the core of G, has k edge-disjoint spanning trees, then κ*(L(G)) ≥ k if and only if κ(L(G)) ≥ max{3, k}. 相似文献
7.
Let G be a graph, $ \{a, b, c\}\subseteq V(G) $, and
$ \{a', b', c'\}\subseteq V(G) $ such that $ \{a, b, c\}\neq \{a', b', c'\} $. We say that
$ (G, \{a, c\}, \{a', c'\}, (b, b')) $ is an obstruction if, for
any three vertex disjoint paths from {a, b, c} to
{a', b', c'} in G, one path is
from b to b'. In this paper
we characterize obstructions. As a consequence, we show that no obstruction can be 8-connected,
unless b = b' or {a, c} = {a', c'}.AMS Subject Classification: 05C38. 相似文献
8.
An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational Experiments 总被引:2,自引:0,他引:2
We present an exact and efficient branch-and-bound algorithm MCR for finding a maximum clique in an arbitrary graph. The algorithm is not specialized for any particular type of graph. It employs approximate coloring to obtain an upper bound on the size of a maximum clique along with an improved appropriate sorting of vertices. We demonstrate by computational experiments on random graphs with up to 15,000 vertices and on DIMACS benchmark graphs that in general, our algorithm decidedly outperforms other existing algorithms. The algorithm has been successfully applied to interesting problems in bioinformatics, image processing, design of quantum circuits, and design of DNA and RNA sequences for biomolecular computation. 相似文献
9.
Shietung Peng Win-tsung Lo 《Journal of Algorithms in Cognition, Informatics and Logic》1996,20(3):445-458
Acoreof a graphGis a pathPinGthat is central with respect to the property of minimizingd(P)=∑v∈V(G)d(v, P), whered(v, P) is the distance from vertexvto pathP. This paper presents efficient algorithms for finding a core of a tree with a specified length. The sequential algorithm runs inO(n log n) time, wherenis the size of the tree. The parallel algorithm runs inO(log2n) time usingO(n) processors on an EREW PRAM model. 相似文献
10.
Mrinmoy Hota Madhumangal Pal Tapan K. Pal 《Computational Optimization and Applications》2001,18(1):49-62
The maximum weight k-independent set problem has applications in many practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design layout and routing problem. Based on DAG (Directed Acyclic Graph) approach, an O(kn
2) time sequential algorithm is designed in this paper to solve the maximum weight k-independent set problem on weighted trapezoid graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph. 相似文献
11.
Xingxing Yu 《Annals of Combinatorics》2003,7(1):105-126
Let G be a graph,{a,b,c} í V(G) \{a,b,c\}\subseteq V(G) , and {a¢,b¢,c¢} í V(G) \{a',b',c'\}\subseteq V(G) such that {a,b,c} 1 {a¢,b¢,c¢} \{a,b,c\}\neq \{a',b',c'\} . We say that (G,{a,c}, {a¢,c¢}, (b, b¢)) (G,\{a,c\}, \{a',c'\}, (b, b')) is an obstruction if, for any three vertex disjoint paths from {a, b, c} to {a', b', c'} in G, one path is from b to b'. In this paper, we characterize a special class of obstructions. This will be used to characterize all obstructions. 相似文献
12.
13.
14.
15.
Amitabh Chaudhary Sundar Vishwanathan 《Journal of Algorithms in Cognition, Informatics and Logic》2001,41(2):404
The achromatic number for a graph G = V, E is the largest integer m such that there is a partition of V into disjoint independent sets {V1, …, Vm} such that for each pair of distinct sets Vi, Vj, Vi Vj is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math.38, 364–372) proved that determining this value for general graphs is NP-complete. For n-vertex graphs we present the first o(n) approximation algorithm for this problem. We also present an O(n5/12) approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees. 相似文献
16.
17.
We deal with the problem of computing in parallel the first K shortest paths from a single origin node to all other nodes of a directed graph. Our approach is based on a very easy way to introduce parallelism in the typical sequential label-correcting method. We describe formally an asynchronous method defined on a shared-memory parallel computational model, and we prove its theoretical correctness under very weak assumptions. According to different strategies used to implement the generic method, we propose several parallel label-correcting algorithms, and we analyze the numerical performance of the resulting codes on a nonuniform memory access multiprocessor via computational results collected on random generated networks. The advantage of parallelism is significant for very large-scale problems of practical interest. 相似文献
18.
Ukrainian Mathematical Journal - We establish effective upper estimates for the maximum products of the inner radii of mutually disjoint domains in (n,m)-radial systems of points of the complex... 相似文献
19.
Daniele Frigioni Alberto Marchetti-Spaccamela Umberto Nanni 《Journal of Algorithms in Cognition, Informatics and Logic》2000,34(2):251
We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal query time. The cost of the update operations depends on the class of the considered graph and on the number of the output updates, i.e., on the number of vertices that, due to an edge modification, either change the distance from the source or change the parent in the shortest paths tree. We first show that, if we deal only with updates on the weights of edges, then the update procedures require O(log n) worst case time per output update for several classes of graphs, as in the case of graphs with bounded genus, bounded arboricity, bounded degree, bounded treewidth, and bounded pagenumber. For general graphs with n vertices and m edges the algorithms require
worst case time per output update. We also show that, if insertions and deletions of edges are allowed, then similar amortized bounds hold. 相似文献
20.
Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems 总被引:1,自引:0,他引:1
In Balas and Niehaus (1996), we have developed a heuristic for generating large cliques in an arbitrary graph, by repeatedly taking two cliques and finding a maximum clique in the subgraph induced by the union of their vertex sets, an operation executable in polynomial time through bipartite matching in the complement of the subgraph. Aggarwal, Orlin and Tai (1997) recognized that the latter operation can be embedded into the framework of a genetic algorithm as an optimized crossover operation. Inspired by their approach, we examine variations of each element of the genetic algorithm—selection, population replacement and mutation—and develop a steady-state genetic algorithm that performs better than its competitors on most problems. 相似文献