Hamming graphs are, by definition, the Cartesian product of complete graphs. In the bipartite case these graphs are hypercubes. We present an algorithm recognizing Hamming graphs in linear time and space. This improve...
详细信息
Hamming graphs are, by definition, the Cartesian product of complete graphs. In the bipartite case these graphs are hypercubes. We present an algorithm recognizing Hamming graphs in linear time and space. This improves a previous algorithm which was linear in time but not in space. This also favorably compares to the general decomposition algorithms of graphs with respect to the Cartesian product, none of which is linear. (C) 1997 Elsevier Science B.V.
An algorithm is presented to answer window queries in a quadtree-based spatial database environment by retrieving all of the quadtree blocks in the underlying spatial database that cover the quadtree blocks that compr...
详细信息
An algorithm is presented to answer window queries in a quadtree-based spatial database environment by retrieving all of the quadtree blocks in the underlying spatial database that cover the quadtree blocks that comprise the window. It works by decomposing the window operation into sub-operations over smaller window partitions. These partitions are the quadtree blocks corresponding to the window. Although a block b in the underlying spatial database may cover several of the smaller window partitions, b is only retrieved once rather than multiple times. This is achieved by using an auxiliary main memory data structure called the active border which requires O(n) additional storage for a window query of size n × n. As a result, the algorithm generates an optimal number of disk I/O requests to answer a window query (i.e., one request per covering quadtree block). A proof of correctness and an analysis of the algorithm's execution time and space requirements are given, as are some experimental results.
We present a new algorithm that finds all primes up to n using at most O(n/log log n) arithmetic operations and O(n/(log n log log n)) space. This algorithm is an improvement of a linear prime number sieve due to Prit...
详细信息
We present a new algorithm that finds all primes up to n using at most O(n/log log n) arithmetic operations and O(n/(log n log log n)) space. This algorithm is an improvement of a linear prime number sieve due to Pritchard. Our new algorithm matches the running time of the best previous prime number sieve, but uses less space by a factor of Theta(log n). In addition, we present the results of our implementations of most known prime number sieves.
Given a set of n disjoint rectangular obstacles in the plane whose edges are either vertical or horizontal, we consider the problem of processing rectilinear approximate shortest path queries between pairs of arbitrar...
详细信息
Given a set of n disjoint rectangular obstacles in the plane whose edges are either vertical or horizontal, we consider the problem of processing rectilinear approximate shortest path queries between pairs of arbitrary query points. Our goal is to answer each approximate shortest path query quickly by constructing a data structure that captures path information in the obstacle-scattered plane. We present a data structure for rectilinear approximate shortest path queries that requires O(n log(2) n) time to construct and O(n log n) space. This data structure enables us to report the length of an approximate shortest path between two arbitrary query points in O(log n) time and the actual path in O(log n + L) time, where L is the number of edges of the output path. If the query points are both obstacle vertices, then the length and an actual path can be reported in O(1) and O(L) time, respectively, The approximation factor for the approximate shortest paths that we compute is 3, The previously best known solution to this problem requires O(n log(3) n) time and O(n log(2) n) space to build a data structure, which supports length and actual path queries respectively in O(log(2) n) and O(log(2) n + L) time (regardless of the types of query points);the approximation factor for paths between arbitrary query points is 7.
A formal proof of convergence of a class of algorithms for reducing inconsistency of painwise comparisons (pc) method is presented. The design of such algorithms is proposed. The convergence of the algorithms justifie...
详细信息
A formal proof of convergence of a class of algorithms for reducing inconsistency of painwise comparisons (pc) method is presented. The design of such algorithms is proposed. The convergence of the algorithms justifies making an inference that iterated modifications of the pc matrix made by human experts should also converge. This is instrumental for credibility of practical applications of the pc method.
This paper is concerned with the fixed-parameter tractability of the problem of deciding whether a graph can be made into a graph with a specified hereditary property by deleting at most i vertices, at most j edges, a...
详细信息
This paper is concerned with the fixed-parameter tractability of the problem of deciding whether a graph can be made into a graph with a specified hereditary property by deleting at most i vertices, at most j edges, and adding at most k edges, where i,j, k are fixed integers. It is shown that this problem is fixed-parameter tractable whenever the hereditary property can be characterized by a finite set of forbidden induced subgraphs. Furthermore, the problem of deciding whether a graph can be made into a chordal graph by adding a fixed number k of edges is shown to be solvable in O(4(k)(k + 1)(-3/2)(m + n)) time, and is thus fixed-parameter tractable.
We present a correction to a previous paper, see [G], on the lower bound for parallel string matching, and improve further the range that the lower bound holds for, from that in [BG], and [G].
We present a correction to a previous paper, see [G], on the lower bound for parallel string matching, and improve further the range that the lower bound holds for, from that in [BG], and [G].
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.
In this paper an O(kn root log c + gamma) time algorithm is presented to solve the maximum weight k-independent set problem on an interval graph with n vertices and non-negative integer weights, where c is the weight ...
详细信息
In this paper an O(kn root log c + gamma) time algorithm is presented to solve the maximum weight k-independent set problem on an interval graph with n vertices and non-negative integer weights, where c is the weight of the longest path of the interval graph and gamma is the total size of all maximal cliques, given its interval representation. If the intervals are not sorted then considering the time for sorting the time complexity is of O(n log n + kn root log c + gamma). Using this algorithm the maximum weight 2-independent set problem for an interval graph with n vertices can be solved in O(n root log c + gamma) time. The best known previous algorithm for 2-independent set problem requires O(n(2)) time.
In this paper, we consider the problem of finding a minimum cost path in a graph. In particular, we consider the perimeter search technique and we investigate the possibility of using very large perimeters. We present...
详细信息
In this paper, we consider the problem of finding a minimum cost path in a graph. In particular, we consider the perimeter search technique and we investigate the possibility of using very large perimeters. We present an algorithm designed to use perimeters of arbitrary size. Our algorithm generates the perimeter incrementally and makes use of a technique called backward pruning for reducing the search effort. A qualitative analysis and experimental results show that our algorithm can effectively use perimeters of very large size.
暂无评论