Results 231 to 240 of about 130,251 (258)
Some of the next articles are maybe not open access.
A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
Lecture Notes in Computer Science, 2009zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Andrzej Lingas, Lingas Andrzej
exaly +2 more sources
An Output-Sensitive Algorithm for Computing Visibility Graphs
SIAM Journal on Computing, 1987Summary: The visibility graph of a set of nonintersecting polygonal obstacles in the plane is an undirected graph whose vertex set consists of the vertices of the obstacles and whose edges are pairs of vertices \((u,v)\) such that the open line segment between \(u\) and \(v\) does not intersect any of the obstacles. The visibility graph is an important
Subir Kumar Ghosh, David M. Mount
openaire +2 more sources
An Output-Sensitive Convex Hull Algorithm for Planar Objects
International Journal of Computational Geometry & Applications, 1998A set of planar objects is said to be of type m if the convex hull of any two objects has its size bounded by 2m. In this paper, we present an algorithm based on the marriage-before-conquest paradigm to compute the convex hull of a set of n planar convex objects of fixed type m. The algorithm is output-sensitive, i.e.
Nielsen, Franck, Yvinec, Mariette
openaire +2 more sources
Output-Sensitive Algorithms for Uniform Partitions of Points
1999We consider the following one- and two-dimensional bucketing problems: Given a set S of n points in R1 or R2 and a positive integer b, distribute the points of S into b equal-size buckets so that the maximum number of points in a bucket is minimized. Suppose at most (n/b) + Δ points lies in each bucket in an optimal solution.
Pankaj K. Agarwal +2 more
openaire +1 more source
An Output-Sensitive Flexible Pattern Discovery Algorithm
2001Given an input sequence of data, a motif is a repeating pattern, possibly interspersed with "dont care" characters and a flexible motif could have a variable (as opposed to fixed) number of "dont care" characters. Given a sequence of records with F fields each, an association rule is a common set of f fields, f ?
Laxmi Parida +2 more
openaire +1 more source
More output-sensitive geometric algorithms
Proceedings 35th Annual Symposium on Foundations of Computer Science, 2002A simple idea for speeding up the computation of extrema of a partially ordered set turns out to have a number of interesting applications in geometric algorithms; the resulting algorithms generally replace an appearance of the input size n in the running time by an output size A/spl les/n.
openaire +1 more source
Parallel and output sensitive algorithms for combinatorial and linear algebra problems
Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures - SPAA '93, 1993This paper gives output-sensitive parallel algorithms whose performance depends on the output size and are significantly more efficient tan previous algorithms for problems with sufficiently small output size. Inputs are n_n matrices over a fixed ground field. Let P(n) and M(n) be the PRAM processor bounds for O(log n) time multiplication of two degree
Joseph Cheriyan, John H. Reif
openaire +1 more source
Designing Output Sensitive Algorithms for Subgraph Enumeration.
The enumeration of all subgraphs respecting some structural property is a fundamental task in theoretical computer science, with practical applications in many branches of data mining and network analysis. It is often of interest to only consider solutions (subgraphs) that are maximal under inclusion, and to achieve output-sensitive complexity, i.e ...Conte, Alessio +5 more
openaire +2 more sources
Space-Efficient and Output-Sensitive Implementations of Greedy Algorithms on Intervals
2017We consider the space-efficient implementation of greedy algorithms for several fundamental problems on intervals. We assume a random access machine model with read-only access to input stored in \(\varTheta (n)\) words of memory, augmented with a random access memory (workspace) of size \(\varTheta (s)\) bits, where \(\lg n \le s \le n\).
Toshiki Saitoh, David G. Kirkpatrick
openaire +1 more source
Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms
2000In this paper, we review and analyze the complexity of a paradigm called grouping-and-querying which has been used in the past for computing convex hulls of points or objects on the plane, maximal and convex layer decompositions, lower envelopes of functions, etc.
openaire +1 more source