Now showing items 7-26 of 37

    • Efficient Planarity Testing 

      Hopcroft, John E.; Tarjan, Robert Endre (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 

      Borodin, Allan B.; Von zur Gathen, Joachim; Hopcroft, John E. (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 

      Hoffmann, Christoph M.; Hopcroft, John E. (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 

      Hoffmann, Christoph M.; Hopcroft, John E. (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 

      Hartmanis, Juris; Hopcroft, John E. (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 

      Hopcroft, John E.; Karp, R. M. (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 

      Hopcroft, John E.; Ullman, Jeffrey D. (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 

      Dietz, Paul F.; Furst, Merrick; Hopcroft, John E. (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 

      Borodin, Allan B.; Hopcroft, John E. (Cornell University, 1981-09)
      A variety of models have been proposed for the study of synchronous parallel computation. We review these models and study further some prototype problems. Within a spectrum of shared memory models, we show that $\log ...
    • Movement Problems for 2-Dimensional Linkages 

      Hopcroft, John E.; Joseph, Deborah A.; Whitesides, Sue H. (Cornell University, 1982-08)
    • A Note on Cryptography and NP$\cap$ CoNP-P 

      Brassard, Giles; Fortune, Steven; Hopcroft, John E. (Cornell University, 1978-04)
      Diffie and Hellman [2] propose the use of the exponential function in a finite field for cryptographic purposes. The proposal is based on the conjecture that the inverse function, the logarithm, is not feasibly computable. ...
    • A Note on Rabin's Nearest-Neighbor Algorithm 

      Fortune, Steven; Hopcroft, John E. (Cornell University, 1978-04)
      Rabin has proposed a probabilistic algorithm for finding the closest pair of a set of points in Euclidean space. His algorithm is asymtomatically linear whereas the best of the known deterministic algorithms take order ...
    • On Edge Coloring Bipartite Graphs 

      Cole, Richard; Hopcroft, John E. (Cornell University, 1980-11)
    • On Minimizing the Number of Multiplications Necessary for Matrix Multiplication 

      Hopcroft, John E.; Kerr, Leslie Robert (Cornell University, 1969-09)
      This paper develops an algorithm to multiply a px2 matrix by a 2xn matrix in $\lceil (3pn+max(n,p))/2 \rceil$ multiplications for matrix multiplication without commutativity. The algorithm minimizes the number of multiplications ...
    • On Planar Point Matching Under Affine Transformation 

      Hopcroft, John E.; Huttenlocher, Daniel P. (Cornell University, 1989-04)
    • On the Equivalence and Containment Problems for Context-Free Languages 

      Hopcroft, John E. (Cornell University, 1968-06)
      Let $G$ and $G_{0}$ be context-free grammars. Necessary and sufficient conditions on $G_{0}$ are obtained for the decidability of $L(G_{0}) \subseteq L(G)$. It is also shown that it is undecidable for which $G_{0},L(G) ...
    • On the Motion of Objects in Contact 

      Hopcroft, John E.; Wilfong, Gordon (Cornell University, 1984-05)
      There is an increasing use of computers in the design, manufacture and manipulation of physical objects. An important aspect of reasoning about such actions concerns the motion of objects in contact. The study of problems ...
    • On the Movement of Robot Arms in Two Dimensional Bounded Regions 

      Hopcroft, John E.; Joseph, Deborah A.; Whitesides, Sue H. (Cornell University, 1982-04)
      The classical mover's problem is the following: can a rigid object in 3-dimensional space be moved from one given position to another while avoiding obstacles? It is known that a more general version of this problem ...
    • On the Reachability Problem for 5-Dimensional Vector Addition Systems 

      Hopcroft, John E.; Pansiot, J. (Cornell University, 1976-06)
      The reachability set for vector addition systems of dimension less than or equal to five are shown to be effectively computable semilinear sets. Thus reachability, equvalence and containment are decidable up to dimension ...
    • On Time Versus Space 

      Hopcroft, John E.; Paul, Wolfgang J.; Valiant, Leslie (Cornell University, 1975-12)
      It is shown that every deterministic multitape Turing machine of time complexity t(n)/log t(n). Consequently, for tape constructable t(n), the class of languages recognizable by multitape Turing machines of time complexity ...