Franco P. Preparata's Publications
2007
Preparata, F., and Domanic, O. A novel approach to the detection of genomic approximate tandem repeats in the Levenshtein metric. Journal of Computational Biology 14, 7 (2007), 873-891.
2006
Preparata, F. Beware of the Model: Reflections on Algorithmic Research. In 6th Conference on Algorithmic Complexity (May 2006), CIAC 2006.
Preparata, F. The Unpredictable Deviousness of Models. In 12th International Computing and Combinatorics Conference. Aug 2006, p. 1.
2005
Preparata, F., Zhang, L., and Choi, K. Quick, practical selection of effective seeds for homology search. Journal of Computational Biology 12, 9 (Oct 2005), 1137-1152. [ pdf ]
Preparata, F., Upfal, E., and Heath, S. Sequence reconstruction from nucleic acid micro-array data. In Analytical Techniques for DNA Sequencing, B. Nunnally, Ed. M. Dekker, 2005, pp. 177-193.
2004
Leong, H., Preparata, F., Sung, W., and Willy, H. Adaptive control of hybridization noise in DNA Sequencing-by-Hybridization. Journal of Bioinformatics and Computational Biology 3, 1 (2004), 1-20. [ pdf ]
Preparata, F., and Oliver, J. DNA sequencing-by-Hybridization using semidegenerate bases. Journal of Computational Biology 11, 4 (2004), 753-765. [ pdf ]
Preparata, F. Sequencing by Hybridization revisited: The analog-spectrum proposal. IEEE-ACM Transactions on Computational Biology and Bioinformatics 1, 1 (2004), 46-52. [ pdf ]
2003
Devillers, O., Mourrain, B., Preparata, F., and Trebuchet, P. Circular Cylinders through four or five points in space. Discrete and Computational Geometry 29, 1 (2003), 83-104. [ pdf ]
Devillers, O., and Preparata, F. Culling a set of points for roundness or cylindricity evaluations. Computational Geometry: Theory and Applications 29, 1 (2003), 83-104.
Heath, S., Preparata, F., and Young, J. Sequencing by hybridization by cooperating direct and reverse spectra. Journal of Computational Biology 10, 3-4 (2003), 499-508. [ pdf ]
Lao, Y., Leong, H., Preparata, F., and Singh, G. Accurate cylindricity evaluation with axis-estimation preprocessing. Precision Engineering 27, 4 (2003), 429. [ pdf ]
2001
Codenotti, B., Leoncini, M., and Preparata, F. The role of arithmetic in fast parallel matrix inversion. Algorithmica 30, 4 (2001), 685-707. [ pdf ]
Fischer, P., Preparata, F., and Savage, J. Generalized scans and tridiagonal systems. Theoretical Computer Science 255 (2001), 423-436. [ pdf ]
2000
Boissonnat, J., and Preparata, F. Robust plane sweeps for intersecting segments. SIAM Journal on Computing 23, 5 (2000), 1401-1421. [ pdf ]
Devillers, O., and Preparata, F. Evaluating the cylindricity of a nominally cylindrical point set. In Proceedings of the Symposium on Discrete Algorithms (Jan 2000), pp. 245-253. [ pdf ]
Preparata, F., and Upfal, E. Sequencing-by-hybridization at the information-theory bound: an optimal algorithm. In Proceedings of the Fourth Annual International Conference on Computational Molecular Biology (Tokyo, Apr 2000), pp. 245-253. [ pdf ]
Preparata, F., and Upfal, E. Sequencing-by-Hybridization at the information-theory bound: an optimal algorithm. Journal of Computational Biology 7, 3-4 (2000), 621-630.
Singh, G., Devillers, O., and Preparata, F. A novel practical approach to cylindricity evaluation: An experimental report. In Proceedings of the Annual Conference of the American Society of Precision Engineering (Oct 2000), pp. 489-492.
1999
Bilardi, G., and Preparata, F. Processor-time tradeoffs under bounded-speed message propagation: Part II, lowerbounds. Theory of Computing Systems 32 (1999), 531-559. [ pdf ]
Chatzi, V., and Preparata, F. Integer-coordinate crystalline meshes. In Proceedings of the Swiss Conference on Computer-Aided Design/Computer-Aided Manufacturing (CAD/CAM) (Neuchatel, Switzerland, Feb 1999), pp. 199-206.
Devillers, O., and Preparata, F. Further results on arithmetic filters for geometric predicates. Computational Geometry: Theory and Applications 13 (1999), 141-148. [ pdf ]
Frieze, A. M., Preparata, F. P., and Upfal, E. Optimal reconstruction of a sequence from its probes. Journal of Computational Biology 6 (1999), 361-368. [ pdf ]
Preparata, F., Frieze, A., and Upfal, E. On the power of universal bases in sequencing by hybridization. In Proceedings of the Third Annual International Conference on Computational Molecular Biology (Lyon, France, Apr 1999), pp. 295-301. [ pdf ]
1998
Devillers, O., Liotta, G., Preparata, F., and Tamassia, R. Checking the convexity of polytopes and the planarity of subdivisions. Computational Geometry: Theory and Applications 11, 3-4 (1998), 187-208. [ pdf ]
Devillers, O., and Preparata, F. A probablislistic analysis of the power of arithmetic filters. Discrete and Computational Geometry 20, 4 (1998), 323-347. [ pdf ]
Liotta, G., Preparata, F., and Tamassia, R. Robust proximity queries: An illustration of degree-driven algorithm design. SIAM Journal on Computing 28, 3 (1998), 864-889. [ pdf ]
1997
Avnaim, F., Boissonnat, J., Devillers, O., Preparata, F., and Yvinec, M. Evaluating signs of determinants using single-precision arithmetic. Algorithmica 17, 2 (Feb 1997), 111-132. [ pdf ]
Bilardi, G., and Preparata, F. Processor-time tradeoffs under bounded-speed message propagation: Part I, upper bounds. Theory of Computing Systems 30 (1997), 523-546. [ pdf ]
Devillers, O., Liotta, G., Preparata, F. P., and Tamassia, R. Checking the Convexity of Polytopes and the Planarity of Subdivisions. In Lecture Notes in Computer Science, Proceedings of the Workshop on Algorithms and Data Structures (WADS) (1997), Springer-Verlag, pp. 186-199. [ pdf ]
Hamano, T., Takagi, N., Yajima, S., and Preparata, F. O(n)-depth circuit algorithm for modular exponentiation. IEEE Transactions on Computers 46, 6 (1997), 701-704.
Liotta, G., Preparata, F. P., and Tamassia, R. Robust Proximity Queries: An Illustration of Degree-driven Algorithm Design. In Proceedings of the ACM Symposium on Computational Geometry (1997), pp. 156-165. [ pdf ]
Pietracaprina, A., and Preparata, F. Practical constructive schemes for deterministic shared-memory access. Theory of Computing Systems 30, 1 (1997), 3-37. [ pdf ]
1996
Apostolico, A., and Preparata, F. Data structures and algorithms for the string statistics problem. Algorithmica 15 (1996), 481-494.
Chiang, Y.-J., Preparata, F. P., and Tamassia, R. A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. SIAM Journal on Computing 25, 1 (1996), 207-233. [ pdf ]
Preparata, F. Lectures on Parallel Computation. Kyoto University, 1996.
Tamassia, R., Liotta, G., and Preparata, F. P. Robust proximity queries in implicit Voronoi diagrams. In Proceedings of the 8th Canadian Conference on Computational Geometry (1996), p. 1. [ pdf ]
Tamassia, R., Agarwal, P., Amato, N., Chen, D., Dobkin, D., Drysdale, R., Fortune, S., Goodrich, M. T., Hershberger, J., O'Rourke, J., Preparata, F., Sack, J.-R., Suri, S., Tollis, I., Vitter, J., and Whitesides, S. Strategic directions in computational geometry. ACM Computing Surveys 28, 4 (1996), 591-606. [ pdf ]
1995
Amato, N. M., and Preparata, F. P. A time-optimal parallel algorithm for three-dimensional convex hulls. Algorithmica 14, 2 (1995), 169-182. [ pdf ]
Bilardi, G., and Preparata, F. P. Horizons of parallel computation. Journal of Parallel and Distributed Computing 27, 2 (1995), 172-182. [ pdf ]
Bilardi, G., and Preparata, F. P. Lower bounds to processor-time tradeoffs under bounded-speed message propagation. In Proceedings of the Workshop on Algorithms and Data Structures (WADS) '95 (1995), pp. 1-12.
Bilardi, G., and Preparata, F. P. Upper bounds to processor-time tradeoffs under bounded-speed message propagation. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures (1995), pp. 185-194. [ pdf ]
Boissonnat, J.-D., Devillers, O., Donati, L., and Preparata, F. P. Motion planning of legged robots: the spider robot problem. International Journal of Computational Geometry and Applications (IJCGA) 5 (1995), 320.
Fischer, P. F., Preparata, F. P., and Savage, J. E. Generalized scans and tri-diagonal systems. In Procs. Symposium on Theoretical Aspects of Computer Science (1995), pp. 168-180. [ pdf ]
Hamano, T., Takagi, N., Yajima, S., and Preparata, F. P. O(n)-depth circuit algorithm for modular exponentiation. In Proceedings of the IEEE Symposium on Computer Arithmetic (1995), pp. 188-192.
Pan, V. Y., and Preparata, F. P. Work-preserving speed-up of parallel matrix computations. SIAM Journal on Computing (SICOMP) 24, 4 (1995), 811-821. [ pdf ]
Preparata, F. P. Should Amdahl's Law be repealed? (Abstract). In Proceedings of the 6th International Symposium on Algorithms and Computation (ISAAC 1995) (1995), p. 311.
1994
Janardan, R., and Preparata, F. P. Widest-corridor problems. Nordic Journal of Computing (NJC) 1, 2 (1994), 231-245.
1993
Amato, N. M., and Preparata, F. P. An NC parallel 3D convex hull algorithm. In Proceedings of the Symposium on Computational Geometry (1993), pp. 289-297. [ pdf ]
Chiang, Y.-J., Preparata, F. P., and Tamassia, R. A unified approach to dynamic point location, ray shooting, and shortest paths in planar maps. In Proceedings of the 4th ACM Society for Industrial and Applied Mathematics Symposium on Discrete Algorithms (1993), pp. 44-53. [ pdf ]
Janardan, R., and Preparata, F. P. Widest-corridor problems. In Proceedings of the Canadian Conference on Computational Geometry (CCCG) (1993), pp. 426-431.
Pietracaprina, A., and Preparata, F. P. On O(sqrt(n)) -worst-case-time solution to the granularity problem. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (1993), pp. 110-119.
Pietracaprina, A., and Preparata, F. P. A practical constructive scheme for deterministic shared-memory access. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures (1993), pp. 100-109. [ pdf ]
Preparata, F. Combinational Networks and Switching Algebra. In The Electrical Engineering Handbook, R. Dorf, Ed. CRC Press, 1993, pp. 1695-1711.
Preparata, F. P., and Vitter, J. S. A Simplified technique for hidden-line elimination in terrains. International Journal of Computational Geometry and Applications (IJCGA) 3, 2 (1993), 167-181. [ pdf ]
1992
Amato, N. M., and Preparata, F. P. The parallel 3D convex hull problem revisited. International Journal of COmputational Geometry and Applications (IJCGA) 2, 2 (1992), 163-173.
Bilardi, G., and Preparata, F. P. Memory requirements of first-order digital filters. IEEE Transactions on Circuits and Systems CS-36, CS-36 (1992), 348-355. [ pdf ]
Boissonnat, J.-D., Devillers, O., and Preparata, F. P. Computing the union of 3-colored triangles. In Proceedings of the 8th ACM Symposium on Computational Geometry (Jun 1992).
Muller, D. E., and Preparata, F. P. Parallel restructuring and evaluation of expressions. Journal of Computer and System Sciences 44, 1 (1992), 43-62.
Pan, V. Y., and Preparata, F. P. Supereffective slow-down of parallel computations. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures (1992), pp. 402-409. [ pdf ]
Preparata, F. P., and Tamassia, R. Efficient point location in a convex spatial cell-complex. SIAM Journal on Computing 21 (1992), 267-280. [ pdf ]
Preparata, F. P., and Bilardi, G. Horizons of parallel computation. In Proceedings of the 25th Anniversary of the French National Institute for Research in Computer Science and Control (INRIA) (1992), pp. 155-174.
Preparata, F. P., Vitter, J. S., and Yvinec, M. Output-sensitive generation of the perspective view of isothetic parallelepipeds. Algorithmica 8, 4 (1992), 257-283.
Preparata, F. P., and Vitter, J. S. A simplified technique for hidden-line elimination in terrains. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (1992), pp. 135-146.
1991
Boissonnat, J.-D., Devillers, O., and Preparata, F. P. Computing the union of 3-colored triangles. International Journal of COmputational Geometry and Applications (IJCGA) 1, 2 (1991), 187-196.
Hornick, S. W., and Preparata, F. P. Deterministic P-RAM simulation with constant redundancy. Information and Computation 92, 1 (1991), 81-96.
Preparata, F. P. Inverting a Vandermonde matrix in minimum parallel time. Information Processing Letters 38, 6 (1991), 291-294.
Zhou, D., Preparata, F. P., and Kang, S. M. Interconnection delay in very high-speed VLSI. IEEE Transactions on Circuits and Systems 28, 7 (Jul 1991), 779-790. [ pdf ]
1990
Alevizos, P., Boissonnat, J.-D., and Preparata, F. P. An optimal algorithm for the boundary of a cell in a union of rays. Algorithmica 5, 4 (1990), 573-590.
Bilardi, G., and Preparata, F. P. Characterization of associative operations with pefix circuits of constant depth and linear size. SIAM Journal on Computing (SICOMP) 19, 2 (1990), 246-255.
Edelsbrunner, H., Preparata, F. P., and West, D. B. Tetrahedrizing Point Sets in Three Dimensions. Journal of Symbolic Computation 10, 4 (1990), 335-348.
Preparata, F. P., Vitter, J. S., and Yvinec, M. Computation of the axial view of a set of isothetic parallelepipeds. ACM Transactions on Graphics 9, 3 (1990), 278-300. [ pdf ]
Preparata, F. P., and Tamassia, R. Dynamic planar point location with optimal query time. Theoretical Computer Science 74 (1990), 95-114.
Preparata, F. P., Vitter, J. S., and Yvinec, M. Output-sensitive generation of the perspective view of isothetic parallelepipeds. In Proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT 1990) (1990), pp. 71-84.
Preparata, F. P., and Vuillemin, J. Practical cellular dividers. IEEE Transactions on Computers 39, 5 (1990), 605-614. [ pdf ]
Preparata, F. P. Planar point location revisited (review paper). International Journal of Foundations of Computer Science 1, 1 (1990), 71.
Tamassia, R., and Preparata, F. P. Dynamic maintenance of planar digraphs, with applications. Algorithmica 5 (1990), 509-527.
1989
Alevizos, P., Boissonnat, J.-D., and Preparata, F. P. On the boundary of a union of rays. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (1989), pp. 72-83.
Bilardi, G., and Preparata, F. P. Size-time complexity of Boolean networks for prefix computations. Journal of the ACM 36, 2 (Apr 1989), 362-382. [ pdf ]
Hornick, S. W., and Preparata, F. P. Deterministic P-RAM simulation with constant redundancy. In Proceedings of the ACM Symposium on Parallel Algorithms and Architectures (1989), pp. 103-109. [ pdf ]
Lee, D. T., and Preparata, F. P. Parallel batched planar point location on the CCC. Information Processing Letters 33, 4 (1989), 175-179.
Nanney, D., Preparata, R., Preparata, F. P., Meyer, E. B., and Simon, E. Shifting ditypic site analysis: heuristics for expanding the phylogenetic range of nucleotide sequences in Sankoff string analysis. Journal of Molecular Evolution 28 (1989), 451-459.
Preparata, R., Meyer, E. B., Preparata, F. P., Vossbrinck, C., Simon, E., and Nanney, D. Ciliate evolution: The ribosomal phylogeny of the Tetrahymenine ciliates. Journal of Molecular Evolution 28 (1989), 427-442.
Preparata, F. P., and Tamassia, R. Dynamic planar point location with optimal query time. In Proceedings on the 6th Symposium on Theoretical Aspects of Computer Science (1989), Springer-Verlag, pp. 84-95.
Preparata, F. P., and Tamassia, R. Efficient spatial point location. In Proceedings of the 1st Workshop on Algorithms and Data Structures (1989), Springer-Verlag, pp. 3-11.
Preparata, F. P., and Tamassia, R. Fully dynamic point location in a monotone subdivision. SIAM Journal on Computing 18, 4 (1989), 811-830. [ pdf ]
Preparata, F. P. Holographic dispersal and recovery of information. IEEE Transactions on Information Theory 35, 5 (1989), 1123. [ pdf ]
Preparata, F., and Muller, D. Parallel Universal Evaluation of Expressions. In Third Italian Conference on Theoretical Computer Science (Nov 1989), pp. 38-41.
1988
Edelsbrunner, H., and Preparata, F. P. Minimum polygonal separation. Information and Computation 77, 3 (1988), 218-232.
Edelsbrunner, H., and Preparata, F. P. Tetrahedrizing point sets in three dimensions. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (1988), pp. 315-331.
Preparata, F. P., and Tamassia, R. Fully dynamic techniques for point location and transitive closure in planar structures. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (1988), pp. 558-567.
Preparata, F. P. Planar point location revisited (A guided tour of a decade of research). In Proceedings of the 8th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (1988), pp. 1-17.
1987
Bilardi, G., and Preparata, F. P. Size-time complexity of Boolean networks for prefix computations. In Proceedings of the 19th ACM Symposium on Theory of Computing (May 1987), pp. 436-443.
Alt, H., Hagerup, T., Mehlhorn, K., and Preparata, F. P. Deterministic simulation of idealized parallel computers on more realistic ones. SIAM Journal on Computing (SICOMP) 16, 5 (1987), 808-835.
Lipski Jr., W., and Preparata, F. P. A unified approach to layout wirability. Mathematical Systems Theory 19, 3 (1987), 189-203.
Mehlhorn, K., and Preparata, F. P. Area-time optimal division for T=O((logn)1+ ε). Information and Computation 72, 3 (1987), 270-282.
Sarrafzadeh, M., and Preparata, F. P. A bottom-up layout technique based on two rectangle routing. Integration: The VLSI Journal 5 (1987), 231-246.
1986
Alt, H., Hagerup, T., Mehlhorn, K., and Preparata, F. P. Deterministic simulation of idealized parallel computers on more realistic ones. In Proceedings of the Conference on Mathematical Foundations of Computer Science (1986), pp. 199-208.
Bilardi, G., and Preparata, F. P. Area-time lower-bound techniques with applications to sorting. Algorithmica 1, 1 (1986), 65-91.
Bilardi, G., and Preparata, F. P. Digital filtering in VLSI. In Algorithms and Architectures, Proceedings of the Very Large-Scale Integration (VLSI) Aegean Workshop on Computing (1986), pp. 1-11.
Chazelle, B., and Preparata, F. P. Halfspace range search: an algorithmic application of k-sets. Discrete & Computational Geometry 1 (1986), 83-93.
Chazelle, B., Cole, R., Preparata, F. P., and Yap, C. New upper bounds for neighbor searching. Information and Control 68, 2 (1986), 105-124.
Mehlhorn, K., Preparata, F. P., and Sarrafzadeh, M. Channel routing in knock-knee mode: simplified algorithms and proofs. Algorithmica 1, 2 (1986), 213-221.
Mehlhorn, K., and Preparata, F. P. Routing through a rectangle. Journal of the ACM 33, 1 (Jan 1986), 60-85.
1985
Apostolico, A., and Preparata, F. P. Structural properties of the string statistics problem. Journal of Computer and System Sciences 31, 3 (1985), 394-411.
Bilardi, G., and Preparata, F. P. The influence of key length on the area-time complexity of sorting. In Proceedings of the 12th Colloquium on Automata, Languages and Programming (1985), pp. 53-62.
Bilardi, G., and Preparata, F. P. A minimum area VLSI network for O(log n) time sorting. IEEE Transactions on Computers 34, 4 (1985), 336-343.
Bilardi, G., and Preparata, F. P. Tessellation techniques for area-time lower bounds with applications to sorting. In Proceedings of the Conference on Information Science and Systems (CISS) (Mar 1985).
Bilardi, G., and Preparata, F. P. The VLSI optimality of the AKS sorting network. Information Processing Letters 20, 2 (1985), 55-59.
Preparata, F. P., and Shamos, M. I. Computational Geometry - An Introduction. Springer, 1985.
Preparata, F. Introduction to Computer Engineering. John Wiley and Sons, 1985.
Sarrafzadeh, M., and Preparata, F. P. Compact channel routing of multiterminal nets. Annals of Discrete Mathematics 25 (1985), 255-280.
1984
Preparata, F. P., and Sarrafzadeh, M. Channel routing of nets of bounded degree. In Proceedings of the International Conference on Very Large-Scale Integration (VLSI) Algorithms and Architectures (May 1984).
Bilardi, G., and Preparata, F. P. An architecture for bitonic sorting with optimal VLSI performance. IEEE Transactions on Computers 33, 7 (1984), 646-651.
Bilardi, G., and Preparata, F. P. A minimum area VLSI network for O(log n) time sorting. In Proceedings of the ACM Symposium on the Theory of Computing (1984), pp. 64-70. [ pdf ]
Lee, D. T., and Preparata, F. P. Computational geometry - a survey. IEEE Transactions on Computers 33, 12 (1984), 1072-1101.
Lee, D. T., and Preparata, F. P. Euclidean shortest paths in the presence of rectilinear barriers. Networks 14 (1984), 393-410.
Preparata, F. P., and Lipski Jr., W. Optimal three-layer channel routing. IEEE Transactions on Computers 33, 5 (1984), 427-437.
Preparata, F. P. VLSI algorithms and architectures. In Proceedings of the Conference on Mathematical Foundations of Computer Science (1984), pp. 149-161.
1983
Apostolico, A., and Preparata, F. P. Optimal off-line detection of repetitions in a string. Theoretical Computer Science 22 (1983), 297-315.
Baudet, G. M., Preparata, F. P., and Vuillemin, J. Area-time optimal VLSI circuits for convolution. IEEE Transactions on Computers 32, 7 (1983), 684-688.
Mehlhorn, K., and Preparata, F. P. Area-time optimal VLSI integer multiplier with minimum computation time. Information and Control 58 (1983), 137-156.
Preparata, F. P. A mesh-connected area-time optimal VLSI multiplier of large integers. IEEE Transactions on Computers 32, 2 (1983), 194-198.
Preparata, F. P. Optimal three-dimensional VLSI layouts. Mathematical Systems Theory 16, 1 (1983), 1-8.
1982
Apostolico, A., and Preparata, F. P. A structure for the statistics of all substrings of a textstring with or without overlap. In Proceedings of the 2nd World Conference on Mathematics at the Service of Man (1982), pp. 104-109.
Bentley, J. L., Faust, M. G., and Preparata, F. P. Approximation algorithms for convex hulls. Communications of the ACM 25, 1 (1982), 64-68.
Bilardi, G., Pracchi, M., and Preparata, F. P. A critique of network speed in VLSI models of computation. IEEE Journal of Solid-State Circuits 17, 4 (Aug 1982), 696-702.
Edelsbrunner, H., Maurer, H. A., Preparata, F. P., Rosenberg, A. L., Welzl, E., and Wood, D. Stabbing line segments. BIT Numerical Mathematics 22, 3 (1982), 274-281.
Lee, D. T., and Preparata, F. P. Euclidean shortest paths in the presence of rectilinear barriers. In Proceedings of the 7th Conference on Graph-theoretic Concepts in Computer Science (1982), pp. 303-313.
Lee, D. T., and Preparata, F. P. An improved algorithm for the rectangle enclosure problem. Journal of Algorithms 3, 3 (1982), 218-224.
Nievergelt, J., and Preparata, F. P. Plane-sweep algorithms for intersecting geometric figures. Communications of the ACM 25, 10 (1982), 739-747.
Preparata, F. Computational Complexity. In MAA Studies in Mathematics, S. Pollock, Ed. 1982.
Preparata, F. P., and Lipski Jr., W. Three layers are enough. In IEEE Foundations of Computer Science '82 (1982), pp. 350-357.
1981
Bilardi, G., Pracchi, M., and Preparata, F. P. A critique and appraisal of VLSI models of computation. In Proceedings of the Carnegie-Mellon University Conference on VLSI Systems and Computations (1981), pp. 81-88.
Lipski Jr., W., and Preparata, F. P. Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Informatica 15 (1981), 329-346.
Lipski Jr., W., and Preparata, F. P. Segments, rectangles, contours. Journal of Algorithms 2, 1 (Mar 1981), 63-76.
Preparata, F. P., and Vuillemin, J. Area-time optimal VLSI networks for computing integer multiplications and Discrete Fourier Transform. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP 81) (1981), pp. 29-40.
Preparata, F. P., and Vuillemin, J. The cube-connected cycles: A versatile network for parallel computation. Communications of the ACM 24, 5 (1981), 300-309.
Preparata, F. P. A new approach to planar point location. SIAM Journal on Computing (SICOMP) 10, 3 (1981), 473-482.
Preparata, F. P., and Supowit, K. J. Testing a simple polygon for monotonicity. Information Processing Letters 12, 4 (1981), 161-164.
1980
Lipski Jr., W., and Preparata, F. P. Finding the contour of a union of iso-oriented rectangles. Journal of Algorithms 1, 3 (1980), 235-246.
Preparata, F., and Vuillemin, J. Area-Time Optimal VLSI Networks for Multiplyin gMatrices (Extended Abstract). In Fourteenth Princeton Conference on Information Sciences and Systems (Mar 1980).
Preparata, F. P., and Vuillemin, J. Area-time optimal VLSI networks for multiplying matrices. Information Processing Letters 11, 2 (1980), 77-80.
Preparata, F. P., and Vuillemin, J. Optimal integrated circuit implementation of triangular matrix inversion. In Proceedings of the International Conference on Parallel Processing (Aug 1980), pp. 211-216.
1979
Lee, D. T., and Preparata, F. P. An optimal algorithm for finding the kernel of a polygon. Journal of the ACM 26, 3 (Jul 1979), 415-421.
Lipski Jr., W., and Preparata, F. P. Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. In Proceedings of the Johns Hopkins Conference on Information Sciences and Systems (Mar 1979), p. 65.
Preparata, F. P., and Vuillemin, J. The cube-connected cycles: A versatile network for parallel computation. In Proceedings of the 20th IEEE Symposium on the Foundations of Computer Science (Oct 1979), pp. 140-147.
Preparata, F. P., and Muller, D. E. Finding the intersection of n half-spaces in time O(n log n). Theoretical Computer Science 8 (1979), 45-55.
Preparata, F. P. A note on locating a set of points in a planar subdivision. SIAM Journal on Computing (SICOMP) 8, 4 (1979), 542-545.
Preparata, F. P. An optimal real-time algorithm for planar convex hulls. Communications of the ACM 22, 7 (1979), 402-405.
1978
Adleman, L. M., Booth, K. S., Preparata, F. P., and Ruzzo, W. L. Improved time and space bounds for Boolean matrix multiplication. Acta Informatica 11 (1978), 61-77.
Garey, M. R., Johnson, D. S., Preparata, F. P., and Tarjan, R. E. Triangulating a simple polygon. Information Processing Letters 7, 4 (1978), 175-179.
Johnson, D. S., and Preparata, F. P. The densest hemisphere problem. Theoretical Computer Science 6 (1978), 93-107.
Lee, D. T., and Preparata, F. P. The all nearest-neighbor problem for convex polygons. Information Processing Letters 7, 4 (1978), 189-192.
Muller, D. E., and Preparata, F. P. Finding the intersection of two convex polyhedra. Theoretical Computer Science 7 (1978), 217-236.
Preparata, F. P., and Sarwate, D. V. An improved parallel processor bound in fast matrix inversion. Information Processing Letters 7, 3 (1978), 148-150.
Preparata, F. P. New parallel sorting schemes. IEEE Transactions on Computers 27, 7 (1978), 669-673.
Preparata, F., and DiEuliis, V. Spectrum Shaping with Codes with Finite Autocorrelation Sequence. IEEE Transactions on Communications 26, 4 (Apr 1978), 474-478.
1977
Lee, D. T., and Preparata, F. P. Location of a point in a planar subdivision and its applications. SIAM Journal on Computing (SICOMP) 6, 3 (1977), 594-606.
Preparata, F. P., and Sarwate, D. V. Computational complexity of Fourier Transforms over finite fields. Mathematics of Computation 31, 139 (Jul 1977), 740-751.
Preparata, F. P., and Hong, S. J. Convex hulls of finite sets of points in two and three dimensions. Communications of the ACM 20, 2 (1977), 87-93.
Preparata, F. P. The medial axis of a simple polygon. In Proceedings of the Conference on the Mathematical Foundations of Computer Science (1977), pp. 443-450.
Preparata, F. Parallelism in Sorting. In Interntaional Conference on Parallel Processing (Aug 1977), pp. 202-205.
Preparata, F. P., Muller, D. E., and Barak, A. Reduction of depth of Boolean networks with a fan-in constraint. IEEE Transactions on Computers 26, 5 (1977), 474-479.
Preparata, F., and DeEuliis, V. Spectrum Shaping with Alphabetic Codes with Finite Autocorrelation Sequence. In 1977 Conference on Information Science Systems (Apr 1977), The John Hopkins University, pp. 274-279.
1976
Galbiati, G., and Preparata, F. P. On permutation-embedding sequences. SIAM Journal of Applied Mathematics 30, 3 (May 1976), 421-423.
Lee, D. T., and Preparata, F. P. Location of a point in a planar subdivision and its applications. In Proceedings of the 8th ACM Automata & Computability Theory Symposium on the Theory of Computation (SIGACT 1976) (May 1976), pp. 231-235.
Luccio, F., and Preparata, F. P. Storage for consecutive retrieval. Information Processing Letters 5, 3 (1976), 68-71.
Muller, D. E., and Preparata, F. P. Restructuring of arithmetic expressions for parallel evaluation. Journal of the ACM 23, 3 (Jul 1976), 534-543.
Preparata, F. P., and Muller, D. E. Efficient parallel evaluation of Boolean expression. IEEE Transactions on Computers 25, 5 (1976), 548-549.
1975
Kung, H. T., Luccio, F., and Preparata, F. P. On finding the maxima of a set of vectors. Journal of the ACM 22, 4 (Oct 1975), 469-476.
Muller, D. E., and Preparata, F. P. Bounds to complexities of networks for sorting and for switching. Journal of the ACM 22, 2 (Apr 1975), 195-201.
Preparata, F. P. A fast stable sorting algorithm with absolutely minimum storage. Theoretical Computer Science 1, 2 (1975), 185-190.
Preparata, F. P., and Muller, D. E. The time required to evaluate division-free arithmetic expressions. Information Processing Letters 3, 5 (1975), 144-146.
1974
Preparata, F. P., and Nievergelt, J. Difference-preserving codes. IEEE Transactions on Information Theory 20, 5 (Sep 1974), 643-649.
Preparata, F. P., and Bellato, L. Length-2 alphabetic codes for spectrum. shaping. In Proceedings of the Zurich Seminar on Digital Communication (1974).
1973
Preparata, F., and Bellato, L. Error Detection and Synchronoization with Pseudoternary Codes for Data Transmission. Alta Frequenza 42, 6 (Jun 1973), 134-139.
Preparata, F. P., and Yeh, R. T. Introduction to Discrete Structures for Computer Science and Engineering. Addison-Wesley Longman Publishing Co., 1973.
Preparata, F. On Multitransmission Networks. IEEE Transactions on Circuit Theory CT-20, 1 (Jan 1973), 67-69.
1972
Muller, D. E., and Preparata, F. P. Minimum delay networks for sorting and for switching. In Proceedings of the Sixth Annual Princeton Conference on Information Sciences and Systems (1972).
Preparata, F. P., and Ray, S. R. An approach to artificial nonsymbolic cognition. Information Sciences 4, 1 (1972), 65-86.
Preparata, F. Analysis of Traffic Flow on a Signalized One-Way Artery. Transportation Science 6, 1 (Feb 1972), 32-51.
Preparata, F. P., and Yeh, R. T. Continuously valued logic. Journal of Computer and System Sciences 6, 5 (1972), 397-418.
Preparata, F. Universal Logic Modules of a New Type. IEEE Transactions on Computers C-21, 6 (Jun 1972), 585-588.
Preparata, F. Universal Logic Modules as an Approach to Functional Standardization. In First Texas Symposium on Computer Systems (Jun 1972).
1971
Preparata, F. P., and Yeh, R. T. Continuously valued logic. In Proceedings of the Symposium on the Theory and Application of Multiple-Valued Logic Design (May 1971), pp. 124-131.
Chien, R. T., Hong, S. J., and Preparata, F. P. Some results in the theory of arithmetic codes. Information and Control 19, 3 (1971), 246-264.
Preparata, F. P., and Muller, D. E. On the delay required to realize Boolean functions. IEEE Transactions on Computers C-20, 4 (Apr 1971), 459-461.
Preparata, F. On the Design of Universal Boolean Functions. IEEE Transactions on Computers C-20, 4 (Apr 1971), 418-423.
Preparata, F. On the Representation of Integers in Nonadjacent Form. SIAM Journal of Applied Mathematics 21, 4 (Dec 1971), 630-635.
Preparata, F. Some Results on Multitransmission Networks. In Fifth Princeton Conference on Information Sciences and Systems (Mar 1971), p. 88.
Preparata, F., and Martelli, A. Thickness and cascade decomposition of permutations (Tolshcina i kaskadnaiya dekomposiziya perestanovok in Russian). Avtomatika i Telemekhanika, 7 (Jul 1971), 98-108.
1970
Preparata, F. On the Design of Universal Logical Networks. In Kyoto International Conference on Circuit and System Theory (Sep 1970).
Preparata, F. P., and Muller, D. E. Generation of near-optimal universal Boolean functions. Journal of Computer and System Sciences 4, 2 (1970), 93-102.
Preparata, F. An Improved Upper-Bound to Free-Distance for Rate 1/N Convolutional Codes. In Mervin J. Kelly Communications Conference (Oct 1970).
Preparata, F. A New Look at the Golay (23,12) Binary Code. IEEE Transactions on Information Theory 16, 4 (Jul 1970), 510-511.
Preparata, F., and Martelli, A. On Thickness and Cascade Decomposition of Permutation Connections. In Kyoto International Conference on Circuit and System Theory (Sep 1970).
1969
Preparata, F. An Estimate of the Length of Diagnostic Tests. IEEE Transactions on Reliability 18, 3 (Aug 1969), 131-136.
Preparata, F. The State Coding Problem of Sequential Networks Revisited. In Twelfth Midwest Symposium on Circuit Theory (Apr 1969), pp. I.5.1-I.5.8.
1968
Chien, R. T., Hong, S. J., and Preparata, F. P. Some contributions to the theory of arithmetic codes. In Proceedings of the First Annual Hawaii International Conference on Systems Sciences (1968).
Chien, R. T., and Preparata, F. P. Search strategy and file organization in computerized information retrieval systems with mass memory. In Mechanized information, Storage, Retrieval, and Dissemination, K. Samuelson, Ed. North-Holland Publishing Co, 1968, pp. 108-121.
Preparata, F. An Alternate Description and a New Decoding Procedure of Nordstrom-Robinson Optimum Code. In Second Princeton Conference on Information Sciences and Systems (Mar 1968), pp. 131-134.
Preparata, F. P. A class of optimum nonlinear double-error-correcting codes. Information and Control 13, 4 (1968), 378-400.
Preparata, F. Convolutional Transformation and Recovery of Binary Sequences. IEEE Transactions on Electronic Computers C-17, 7 (Jul 1968), 649-655.
Preparata, F. Some Results on Sequentially Diagnosable Systems. In Hawaii International Conference on System Sciences (Jan 1968), pp. 623-626.
Preparata, F. P. Weight and distance structure of Nordstrom-Robinson quadratic code. Information and Control 12, 5 (1968), 466-473.
1967
Chien, R., and Preparata, F. Search Strategy and File Organization in Computerized Information Retrieval Systems with Mass Memory. In Proceedings of the Fédération internationale de la Documentation and International Federation for Information Processing (FID/IFIP) Joint Conference (Jun 1967), pp. 108-121.
Preparata, F. P., Metze, G., and Chien, R. T. On the connection assignment problem of diagnosable systems. IEEE Transactions on Computers EC-16, 6 (Dec 1967), 848-854.
Preparata, F. P., and Chien, R. T. On clustering techniques of citation graphs. In Proceedings of the First Princeton Conference on Information Sciences and Systems (Mar 1967).
1966
Chien, R., and Preparata, F. Topological Structures of Information Retrieval Systems. In Fourth Allerton Conference on Circuit and System Theory (Oct 1966), pp. 359-367.
Preparata, F. Convolutional Transformation of Binary Sequences: Boolean Functions and their Resynchronizing Properties. IEEE Transactions on Electronic Computers EC-15, 6 (Dec 1966), 898-908.
Preparata, F. A Note on Non-Singular Autonomous Sequential Networks and Invertible Boolean Systems. Ciencias de la Informacion y la Computation 1, 2 (Sep 1966), 25-29.
1965
Preparata, F. On the Realizability of Special Classes of Autonomous Sequential Networks. IEEE Transactions on Electronic Computers EC-14, 6 (Dec 1965), 791-797.
Preparata, F. Traffic Analysis of a Buffered Digital Data Acquisition System. Calcolo 2, 1 (Jan 1965), 113-126.
1964
Preparata, F. Systematic Construction of Optimal Linear Recurrent Codes for Burst Error Correction. Calcolo 1, 2 (Jun 1964), 147-153.
Preparata, F. State-Logic Relations for Autonomous Sequential Networks. IEEE Transactions on Electronic Computers EC-13, 5 (Oct 1964), 542-548.
1962
Preparata, F. Probability of Undetected Errors in Punched-Card Read-Checking Electronic Computers (in Italian). Schede Perforate e Calcolo Electtronico 5 (Mar 1962).
| Page Owner: Franco P. Preparata | Last Modified: Fri Nov 3 15:46:54 2006 |