Discrete Algorithms and Complexity

Proceedings of the Japan-US Joint Seminar, June 4 – 6, 1986, Kyoto, Japan

David S. Johnson, Takao Nishizeki, Akihiro Nozaki

• Publisher: Academic Press
• Year: 2014
• Print ISBN:
  9780123868701
• eBook ISBN:
  9781483274003
• Topic: Mathematics
• Subtopic: Mathematics General
• Index: Mathematics

Perspectives in Computing, Volume 15: Discrete Algorithms and Complexity provides an understanding of discrete algorithms and complexity. This book covers a variety of topics, including discrete logarithm algorithms, parallel bubbling, electronic prototyping, number theoretic complexity, and linear programming. Organized into 27 chapters, this volume begins with an overview of the basic solutions of the primal and dual that can be characterized in graph-theoretic terms. This text then explores the principal partition of vertex-weighted graphs, which is utilized to solve certain assignment problems or flow problems that are formulated using such graphs. Other chapters consider a polynomial-time algorithm for finding the geodesic center of a simple polygon. This book discusses as well the three efficient algorithms for the routing problems around a rectangle. The final chapter deals with a snoopy cache multiprocessor system wherein each processor has a cache in which it stores blocks of data. This book is a valuable resource for mathematicians and researchers.

Table of contents

• Front Cover
• Discrete Algorithms and Complexity
• Copyright Page
• Table of Contents
• Contributors
• Foreword
• Chapter 1. An Upper Bound on the Expected Cost of an Optimal Assignment
• Chapter 2. The Principal Partition of Vertex-Weighted Graphs and Its Applications
• Chapter 3. Generalized Colorings
• Chapter 4. Voronoi Diagram for Points in a Simple Polygon
• Chapter 5. Computing the Geodesic Center of a Simple Polygon
• Chapter 6. On deleting vertices to make a graph of positive genus planar
• Chapter 7. Algorithms for Routing around a Rectangle
• Chapter 8. A Remark on the Complexity of the Knapsack Problem
• Chapter 9. Fast, Rigorous Factorisation and Diecrete Logarltha Algoritluas
• Chapter 10. Redundant Coding for Local Computability
• Chapter 11. SOME PROPERTIES OF THE PARALLEL BUBBLING ΑΝD PARALLEL SORTS ON A MESH—OONNEOTEOD ROOESSOR ARRAY
• Chapter 12. Game Solving Procedure H Is Unsurpassed
• Chapter 13. Algorithmic Problems in Modeling and Electronic Prototyping
• Chapter 14. Complementary Approaches to CNF Boolean Equations
• Chapter 15. Open Problems in Number Theoretic Complexity
• Chapter 16. Decision Problem of the Security for Cryptographic Protocols
• Chapter 17. A Digital Signature Scheme Secure Against Adaptive Chosen Message Attack
• Chapter 18. Are problems having a polynomial time upper bound actually thought to be feasible ?
• Chapter 19. On Probability that a Randomly Selected Set Has Some complexity-Theoretical Property
• Chapter 20. Ranking Rooted Trees, and a Graceful Application
• Chapter 21. Dynamic Search in Graphs
• Chapter 22. Dynamic Search in Graphs
• Chapter 23. A Leaf-Size Hierarchy of Two-Dimensional Alternating Turing Machines
• CHAPTER 24. SIMPLE PROGRAMS WITH A FIXED NUMBER OF VARIABLES SEEM STILL HARD TO ANALYZE
• Chapter 25. Theory of the Multiplicative Penalty Function Method for Linear Programming
• Chapter 26. Linear-time Computability of Combinatorial Problems on Generalized-Series-Parallel Graphs
• Chapter 27. COMPETITIVE SNOOPY CACHING
• PERSPECTIVES IN COMPUTING