Discrete Algorithms and Complexity
Proceedings of the Japan-US Joint Seminar, June 4 - 6, 1986, Kyoto, Japan
Published on 10. May 2014
496 pages
978-1-4832-7400-3 (ISBN)
Description
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.
More details
Other editions
Additional editions
David S. Johnson | etc.
Discrete Algorithms and Complexity
Book
01/1987
Academic Press
€74.90
Article exhausted; check different version
Content
¿ContributorsForewordAn Upper Bound on the Expected Cost of an Optimal AssignmentThe Principal Partition of Vertex-Weighted Graphs and Its ApplicationsGeneralized ColoringsVoronoi Diagram for Points in a Simple PolygonComputing the Geodesic Center of a Simple PolygonOn Deleting Vertices to Make a Graph of Positive Genus PlanarAlgorithms for Routing around a Rectangle (Extended Abstract)A Remark on the Complexity of the Knapsack ProblemFast, Rigorous Factorization and Discrete Logarithm AlgorithmsRedundant Coding for Local ComputabilitySome Properties of the Parallel Bubbling and Parallel Sorts on a Mesh-Connected Processor ArrayGame Solving Procedure H* Is UnsurpassedAlgorithmic Problems in Modeling and Electronic PrototypingComplementary Approaches to CNF Boolean EquationsOpen Problems in Number Theoretic Complexity (Preliminary Version)Decision Problem of the Security for Cryptographic ProtocolsA 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 PropertyRanking Rooted Trees and a Graceful ApplicationDynamic Search in GraphsA Leaf-Size Hierarchy of Two-Dimensional Alternating Turing MachinesSimple Programs with a Fixed Number of Variables Seem Still Hard to AnalyzeTheory of the Multiplicative Penalty Function Method for Linear ProgrammingLinear-Time Computability of Combinatorial Problems on Generalized Series-Parallel GraphsCompetitive Snoopy Caching
