Discrete Algorithms and Complexity - 1st Edition - ISBN: 9780123868701, 9781483274003

Discrete Algorithms and Complexity

1st Edition

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

Editors: David S. Johnson Takao Nishizeki Akihiro Nozaki
eBook ISBN: 9781483274003
Imprint: Academic Press
Published Date: 9th March 1987
Page Count: 496
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


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



An Upper Bound on the Expected Cost of an Optimal Assignment

The Principal Partition of Vertex-Weighted Graphs and Its Applications

Generalized Colorings

Voronoi Diagram for Points in a Simple Polygon

Computing the Geodesic Center of a Simple Polygon

On Deleting Vertices to Make a Graph of Positive Genus Planar

Algorithms for Routing around a Rectangle (Extended Abstract)

A Remark on the Complexity of the Knapsack Problem

Fast, Rigorous Factorization and Discrete Logarithm Algorithms

Redundant Coding for Local Computability

Some Properties of the Parallel Bubbling and Parallel Sorts on a Mesh-Connected Processor Array

Game Solving Procedure H* Is Unsurpassed

Algorithmic Problems in Modeling and Electronic Prototyping

Complementary Approaches to CNF Boolean Equations

Open Problems in Number Theoretic Complexity (Preliminary Version)

Decision Problem of the Security for Cryptographic Protocols

A Digital Signature Scheme Secure Against Adaptive Chosen Message Attack (Extended Abstract)

Are Problems Having a Polynomial Time Upper Bound Actually Thought to Be Feasible?

On Probability that a Randomly Selected Set Has Some Complexity Theoretical Property

Ranking Rooted Trees and a Graceful Application

Dynamic Search in Graphs

A Leaf-Size Hierarchy of Two-Dimensional Alternating Turing Machines

Simple Programs with a Fixed Number of Variables Seem Still Hard to Analyze

Theory of the Multiplicative Penalty Function Method for Linear Programming

Linear-Time Computability of Combinatorial Problems on Generalized Series-Parallel Graphs

Competitive Snoopy Caching


No. of pages:
© Academic Press 1987
Academic Press
eBook ISBN:

About the Editor

David S. Johnson

Takao Nishizeki

Akihiro Nozaki

Ratings and Reviews