Efficient Algorithms for Maximum Regression Depth

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 ² 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.     

Efficient Hybrid Algorithms for Finding Zeros of Convex Functions

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.     

Disjoint Paths in Decomposable Digraphs

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].     

Efficient Batch Job Scheduling in Grids Using Cellular Memetic Algorithms

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: ).     

Short Disjoint Paths in Locally Connected Graphs

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.     

On Spanning Disjoint Paths in Line Graphs

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 ₀, the core of G, has k edge-disjoint spanning trees, then κ*(L(G)) ≥ k if and only if κ(L(G)) ≥ max{3, k}.     

Disjoint Paths in Graphs III,Characterization

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.     

An Efficient Branch-and-bound Algorithm for Finding a Maximum Clique with Computational Experiments

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.     

Efficient Algorithms for Finding a Core of a Tree with a Specified Length

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(log²n) time usingO(n) processors on an EREW PRAM model.     

An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs

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 ²) 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.     

Disjoint Paths in Graphs II,A Special Case

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.     

度和与图中具有给定阶数的点不交的路

设G是一个n阶图，n=∑^ki=1ni，其中,ni≥2(i=1,2,…，k）是整数。我们利用度和给出图G中存在n1,n2，…，nk阶点不交路的充分条件。     

Approximation Algorithms for the Achromatic Number

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 {V₁, …, V_m} such that for each pair of distinct sets V_i, V_j, V_i V_j 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(n^5/12) approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees.     

最小树的一般算法

本文根据设计并行算法的基本原则,给出了最小树的两个对偶定理.在此基础上,建立了两种对偶的同步并行算法的雏型.这两种算法恰恰在对偶的意义下,概括了以往的最小树算法.     

Parallel Asynchronous Algorithms for the K Shortest Paths Problem

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.     

Estimation of the Maximum Product of Inner Radii of Mutually Disjoint Domains

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...     

Fully Dynamic Algorithms for Maintaining Shortest Paths Trees

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.     

Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems

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.