Discrete Algorithms and Complexity
Proceedings of the Japan-US Joint Seminar, June 4 – 6, 1986, Kyoto, Japan
- 1st Edition - March 9, 1987
- Imprint: Academic Press
- Editors: David S. Johnson, Takao Nishizeki, Akihiro Nozaki
- Language: English
- Paperback ISBN:9 7 8 - 1 - 4 8 3 2 - 4 1 1 3 - 5
- eBook ISBN:9 7 8 - 1 - 4 8 3 2 - 7 4 0 0 - 3
Perspectives in Computing, Volume 15: Discrete Algorithms and Complexity provides an understanding of discrete algorithms and complexity. This book covers a variety of topics,… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quotePerspectives 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.
Contributors
Foreword
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
- Edition: 1
- Published: March 9, 1987
- No. of pages (eBook): 496
- Imprint: Academic Press
- Language: English
- Paperback ISBN: 9781483241135
- eBook ISBN: 9781483274003
Read Discrete Algorithms and Complexity on ScienceDirect