Now showing items 1-20 of 37

• #### Automatic Surface Generation in Computer Aided Design ﻿

(Cornell University, 1985-01)
No abstract available
• #### The Complexity of Equivalence and Containment for Free Single Variable Program Schemes ﻿

(Cornell University, 1977-05)
Non-containment for free single variable program schemes is shown to be NP-complete. A polynomial time algorithm for deciding equivalence of two free schemes, provided one of them has the predicates appearing in the same ...
• #### A Conversation with John E. Hopcroft ﻿

(Internet-First University Press, 2015-07-21)
This ACM Turing Award recipient talks about research, textbooks, working with graduate students, his role as a senior statesman of his field and concludes with some words of wisdom.
• #### Determining Points of a Circular Region Reachable by Joints of a Robot Arm ﻿

(Cornell University, 1982-08)
An "arm" is a sequence of links whose endpoints are connected consecutively by movable joints. The location of the first endpoint is fixed. This report gives a polynomial time algorithm for determining the regions that ...
• #### Dividing a Graph into Triconnected Components ﻿

(Cornell University, 1974-02)
An algorithm for dividing a graph into triconnected components is presented. When implemented on a random access computer, the algorithm requires $O(V+E)$ time and space to analyze a graph with $V$ vertices and $E$ edges. ...
• #### Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms ﻿

(Cornell University, 1972-10)
The paper considers the complexity of bilinear forms in a noncommutative ring. The dual of a computation is defined and applied to matrix multiplication and other bilinear forms. It is shown that the dual of an optimal ...
• #### Efficient Planarity Testing ﻿

(Cornell University, 1973-04)
This paper describes an efficient algorithm to determine whether an arbitrary graph G can be embedded in the plane. The algorithm may be viewed as an iterative version of a method originally proposed by Auslander and Parter ...
• #### Fast Parallel Matrix and GCD Computations ﻿

(Cornell University, 1982-04)
We present parallel algorithms to compute the determinant and characteristic polynomial of n x n-matrices and the gcd of polynomials of degree $\leq$n. The algorithms use parallel time $O(\log^{2}n)$ and a polynomial ...
• #### Geometric Ambiguities in Boundary Representations ﻿

(Cornell University, 1986-01)
Boundary representations are usually separated into two components, a topological component and a geometric component. The conditions necessary to insure that the topological component is unambiguous are well understood. ...
• #### The Geometry of Projective Blending Surfaces ﻿

(Cornell University, 1986-05)
Blending surfaces smoothly join two or more primary surfaces that otherwise would intersect in edges. We outline the potential method for deriving blending surfaces, and explain why the method needs to be considered in ...
• #### Independence Results in Computer Science ﻿

(Cornell University, 1976-12)
In this note we show that instances of problems which appear naturally in computer science cannot be answered in formalized set theory. We show, for example, that some relativized versions of the famous P = NP problem ...
• #### A Linear Algorithm for Testing Equivalence of Finite Automata ﻿

(Cornell University, 1971-12)
An algorithm is given for determining if two finite automata with start states are equivalent. The asymptotic running time of the algorithm is bounded by a constant times the product of the number of states of the larger ...
• #### A Linear List Merging Algorithm ﻿

(2008-05-14)
A linear list merging algorithm and its analysis is presented. Starting with n lists, each containing a single element, the algorithm will execute an arbitrary sequence of requests to merge lists and to find the name of ...
• #### A Linear Time Algorithm for the Generalized Consecutive Retrieval Problem ﻿

(Cornell University, 1979-07)
THe Generalized Consecutive Retrieval Problem (GCRP) is to find a directed tree on $n$ records in which each of $k$ subsets forms a directed path. The problem arises in organizing information for efficient retrieval. A ...
• #### Merging on Parallel Models of Computation ﻿

(Cornell University, 1981-09)