A linear time sequential algorithm for finding a straight line that bisects 2 given disjoint convex polygons is presented. The solution can be generalized to other measures and other proportions of cutting. When the...
详细信息
A linear time sequential algorithm for finding a straight line that bisects 2 given disjoint convex polygons is presented. The solution can be generalized to other measures and other proportions of cutting. When the so-called ham-sandwich problem is studied in 3-dimensional space, a plane is found that cuts each of 3 given disjoint convex polyhedra into 2 parts of equal volume. It is believed that only discrete versions of a related problem, cutting 2 regions by a straight line into 2 subregions containing the same number of points, have been studied in Edelsbrunner (1987) and Megiddo (1985).
It is well known that, although all NP-complete decision problems are polynomially isomorphic and in a certain sense equally difficult, the corresponding NP-hard optimization problems can behave in a very different wa...
详细信息
It is well known that, although all NP-complete decision problems are polynomially isomorphic and in a certain sense equally difficult, the corresponding NP-hard optimization problems can behave in a very different way with respect to approximation properties. Recently, the complexity and the computational power of the local search technique in the approximation of NP-hard optimization problems has been studied. The power of local search is investigated by studying the maximum general satisfiability (Max GSAT), which is a generalized version of the maximum satisfiability. It is shown that, by using a relaxed form of local search, a guaranteed quality of approximation can be achieved. It is first shown that, by relaxing the definition of bounded neighborhood, a local search heuristic exists for Max GSAT. It is then proved that using a different objective function a general local search algorithm exists for Max GSAT.
作者：
MYOUPO, JFLRI
CNRS URA 410 Bat. 490 Univ. Paris-Sud 91405 Orsay France
In this paper, we develop a variant of the linear algorithm by I.V. Ramakrishnan and P.J. Varman (Proc. Internat. Conf. on Parallel Processing, 1984) for dynamic programming problems. It requires n cells and n2 + n2 -...
详细信息
In this paper, we develop a variant of the linear algorithm by I.V. Ramakrishnan and P.J. Varman (Proc. Internat. Conf. on Parallel Processing, 1984) for dynamic programming problems. It requires n cells and n2 + n2 - 2 time steps for its execution. Which is better than the 2n2 + 2n - 2 time steps required by the execution of the original algorithm.
We consider the problem of maintaining, using first-order formulas but without auxiliary relations, the transitive closure of directed graphs after the deletion of sets of edges and nodes;earlier results focused on ed...
详细信息
We consider the problem of maintaining, using first-order formulas but without auxiliary relations, the transitive closure of directed graphs after the deletion of sets of edges and nodes;earlier results focused on edge-set insertions and single edge deletions. We give a generic result which asserts maintainability after deleting any ''antichain'' of edges. Many maintainability results follow, including after deleting any edge from acyclic graphs, after deleting any subset of all incoming (outgoing) edges to (from) any antichain family of strongly connected components (SCC), and after deleting any antichain of nodes. We then shaw maintainability after deleting all edges (or nodes) in any antichain family of SCCs. Finally, we show that maintainability after node deletions is at least as hard as after edge deletions. (C) 1997 Elsevier Science B.V.
Let x denote a given nonempty string of length n = Absolute value of x greater-than-or-equal-to 1. A string u is a cover of x if and only if every position of x lies within an occurrence of u within x. Thus x is alway...
详细信息
Let x denote a given nonempty string of length n = Absolute value of x greater-than-or-equal-to 1. A string u is a cover of x if and only if every position of x lies within an occurrence of u within x. Thus x is always a cover of itself. In this paper we characterize all the covers of x in terms of an easily computed normal form for x. The characterization theorem then gives rise to a simple recursive algorithm which computes all the covers of x in time THETA(n).
We consider on-line construction of the suffix tree for a parameterized string, where we always have the suffix tree of the input string read so far. This situation often arises from source code management systems whe...
详细信息
We consider on-line construction of the suffix tree for a parameterized string, where we always have the suffix tree of the input string read so far. This situation often arises from source code management systems where, for example, a source code repository is gradually increasing in its size as users commit new codes into the repository day by day. We present an on-line algorithm which constructs a parameterized suffix tree in randomized O(n) time, where n is the length of the input string. Our algorithm is the first randomized linear time algorithm for the on-line construction problem. (C) 2010 Elsevier B.V. All rights reserved.
We propose a combination of Kleene's three-valued logic and ACP process algebra via the guarded command construct. We present an operational semantics in SOS-style, and a completeness result. (C) 1998 Elsevier Sci...
详细信息
We propose a combination of Kleene's three-valued logic and ACP process algebra via the guarded command construct. We present an operational semantics in SOS-style, and a completeness result. (C) 1998 Elsevier Science B.V. All rights reserved.
We develop a parallel algorithm for the domatic partition problem on interval graphs under the EREW PRAM model. Given a set of n intervals with their 2n endpoints sorted, our algorithm takes 0(log n) time and O(n /log...
详细信息
We develop a parallel algorithm for the domatic partition problem on interval graphs under the EREW PRAM model. Given a set of n intervals with their 2n endpoints sorted, our algorithm takes 0(log n) time and O(n /log n) processors. The cost (time-processor product) of our algorithm is 0(n). Therefore our parallel algorithm is optimal. If these n intervals are not sorted, we can solve this problem in 0(log n) time by using 0(n) processors. This is optimal too. Our algorithm is based on some observations about the degrees of the intervals. These observations result in a very elegant parallel algorithm.
An analysis seeks to find a collision-free trajectory for circular robots such that the trajectory satisfies the robots' centrifugal force and speed requirements. The analysis constructs the trajectory in 2 phase...
详细信息
An analysis seeks to find a collision-free trajectory for circular robots such that the trajectory satisfies the robots' centrifugal force and speed requirements. The analysis constructs the trajectory in 2 phases, with the path in phase one meeting the constraint that all segments of the path have the same length and any 2 adjacent ones are collinear or meet at an angle of 120 degrees. In the 2nd phase, the analysis simply joins 2 adjacent segments by an arc if they are not collinear. The analysis focuses on hexagon space, denoted by H-space, which is a subdivision of terrains into uniform hexagons.
We propose a probabilistic network model, called asynchronous bounded expected delay (ABE), which requires a known bound on the expected message delay. In ABE networks all asynchronous executions are possible, but exe...
详细信息
We propose a probabilistic network model, called asynchronous bounded expected delay (ABE), which requires a known bound on the expected message delay. In ABE networks all asynchronous executions are possible, but executions with extremely long delays are less probable. Thus, the ABE model captures asynchrony that occurs in sensor networks and ad-hoc networks. At the example of an election algorithm, we show that the minimal assumptions of ABE networks are sufficient for the development of efficient algorithms. For anonymous, unidirectional ABE rings of known size n we devise a probabilistic election algorithm having average message and time complexity O(n). (C) 2011 Elsevier B.V. All rights reserved.
暂无评论