Discrete Algorithms and Complexity (eBook)

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

David S. Johnson, Takao Nishizeki, Akihiro Nozaki (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
496 Seiten
Elsevier Science (Verlag)
978-1-4832-7400-3 (ISBN)

Infos

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.

Inhalt

Front Cover 1
Discrete Algorithms and Complexity 4
Copyright Page 5
Table of Contents 6
Contributors 8
Foreword 12
Chapter 1. An Upper Bound on the Expected Cost of an Optimal Assignment 14
Introduction 14
A Regularity Condition 14
The Transportation Problem and its Dual 15
Acknowledgement 17
References 17
Chapter 2. The Principal Partition of Vertex-Weighted Graphs and Its Applications 18
1. Introduction 18
2. The Principal Partition of Vertex-Weighted Graphs and Solution Algorithms For Problem 2 23
3. Flow Assignment In The Graph Defined For Problem 4: Part 1 27
4. Flow Assignment In The Graph Defined For Problem 4: Part 
35 
5. Applications 43
6. Concluding Remarks 45
References 46
Chapter 3. Generalized Colorings 48
0. Introduction 48
1. Parameters 50
2. Algorithmic Issues 54
3. Obstructions 56
4. The Homomorphism Order 58
REFERENCES 59
Chapter 4. Voronoi Diagram for Points in a Simple Polygon 64
1. Introduction 64
2. Sketch of the algorithm 66
3. Constructing the weighted Voronoi diagram 71
References 76
Chapter 5. Computing the Geodesic Center of a 
78 
1. Introduction 78
2. Uniqueness of Geodesic Center 80
3. Geodesic Diameter of a Simple Polygon 85
4. Farthest-Point Voronoi Diagra 85
References 90
Chapter 6. On deleting vertices to make a graph of positive genus planar 94
1. Introduction 94
2. Background in topologioal graph theory and order arithmetic 96
3. The main result 103
4. Conclusion 109
References 110
Chapter 7. Algorithms for Routing around a Rectangle 112
1. Introduction 112
2. Edge-disjoint paths 113
3. Routing 114
4. Minimum area routing 114
References 116
Chapter 8. A Remark on the Complexity of the Knapsack Problem 120
1. Introduction 121
2. The Basic Algorithm and a Restricted Modification 122
3. The Three List Problem and its Relation to the Knapsack Problem 125
References 131
Chapter 9. Fast, Rigorous Factorisation and Diecrete Logarltha Algoritluas 132
1. Introduction 132
2. A riaoroua version of the elliptic curve factorina 
135 
3. Factoring with random squares 140
4. Discrete logarithes In GF(p) 147
5. DISCRETE LOGARITHMS OVER 
153 
REFERENCES 154
Chapter 10. Redundant Coding for Local Computability 158
1. Introduction 158
2. Coding and Local Computability 160
3. Addition on Residue Class 162
4. High-speed Parallel Computation of Operations on Finite Abelian Group 168
5. Applications 170
6. Conclusion 171
Acknowledgement 171
References 171
Chapter 11. SOME PROPERTIES OF THE PARALLEL BUBBLING ..D PARALLEL SORTS ON A MESH—OONNEOTEOD ROOESSOR ARRAY 174
1. Introduction 174
2. Properties of the parallel bubbling 175
3. Sorting on a mesh-connected processor array 179
4· Lower Bounds on Computing Times 191
5. Concluding remarks 195
References 196
Chapter 12. Game Solving Procedure H 
198 
1. Introduction 198
2. Game Trees and Search Procedures 199
3. Outline of the Proof 202
4. Proof for Case A 204
5. Proof for Case . 206
6. Some Properties of 
208 
7. Proof for Case C 210
References 213
Chapter 13. Algorithmic Problems in Modeling and Electronic Prototyping 214
Introduction 215
Electronic Prototyping 219
Structuring a System 220
Representing a Physical Object 223
References 234
Chapter 14. Complementary Approaches to CNF Boolean Equations 236
1. Introduction 236
2. Preliminaries 239
3. IS approach and its complementary nature 241
Acknowledgements 247
References 247
Chapter 15. Open Problems in Number Theoretic Complexity 250
Introduction 250
Definitions, notation, and conventions 251
1. Primality testing 254
2. Testing an inflnite set of primes 255
3. Prime greater than a given bound 255
4. Prime in an arithmetic progression 256
5. Integer factoring 256
6. Factoring a set of positive density 257
7. Squarefree part 257
8. Squarefreeness 258
9. Number of distinct prime factors 258
10. Roots modulo a composite 259
11. Quadratic residuosity modulo a composite 259
12. Quadratic non-residue modulo a prime 259
13. Quadratic signature 260
14. Square roots modulo a prime 261
15. Polynomial roots modulo a prime 261
16. Factoring polynomials modulo a prime 261
17. Irreducible polynomials 262
18. Recognition of a primitive root modulo a prime 262
19. Finding a primitive root modulo a prime 263
20. Calculation or orders modulo a prime 263
21. Discrete logarithm modulo a prime 263
22. Discrete logarithm modulo a composite 264
23. Calculation of f(.) 264
24. Point on an elliptic curve 264
25. Binary quadratic congruences 265
26. Key distribution 266
27. Construction of an elliptic curve group of a given order 266
28. Discrete logarithms in elliptic curve groups 266
29· Shortest vector in a lattice 267
30. Short vector in a lattice 267
31. Galois group of a polynomial 267
32. Class numbers 268
33. Solvability of binary quadratic diophantine equations 268
34. Solvability of anti-Pellian equation 269
35. Greatest common divisors in parallel 269
36. Integer multiplication in linear time 269
References 270
Chapter 16. Decision Problem of the Security for Cryptographic Protocols 276
1. Introduotion 276
2. Formal Definition of the Security Problem 277
3. Undecidabllity of the Security Problem SP 281
5. A Simple Sufficient Condition under imich the Security Problem Is Decldable 285
6. Sufficient Condition Under Which the Security Problem 
290 
7. Conclusion 297
References 298
Chapter 17. A Digital Signature Scheme Secure Against 
300 
I. INTRODUCTION 300
II. FUNDAMENTAL NOTIONS 302
III. PREVIOUS SIGNATURE SCHEMES AND THEIR SECURITY 304
IV. THE PARADOX OF PROVING SIGNATURE SCHEMES SECURE 306
V. GENERAL NOTATION AND CONVENTIONS 307
VI. THE COMPLEXITY THEORETIC BASIS OF THE NEW SCHEME 308
VII. BUILDING BLOCKS FOR SIGNING 314
VIII. DESCRIPTION OF OUR SIGNATURE SCHEME 315
IX. PROOF OF SECURITY 318
X. Variations and Improvements 318
XI. Open Problems 320
XII. Acknowledgements 321
XIII. References 321
Chapter 18. Are problems having a polynomial time upper bound actually thought to be feasible ? 324
1. Introduction 324
2. Preliminaries 325
3. Results 327
Concluding Remarks 333
References 334
Chapter 19. On Probability that a Randomly Selected Set Has Some complexity-Theoretical Property 338
1. Introduction 338
2. Preliminaries 340
3. Main results 341
Acknowledgments 352
References 352
Chapter 20. Ranking Rooted Trees, and a Graceful Application 354
1. Introduction 355
2. Preliminaries 355
3. Ranking rooted trees 357
4. Graceful trees 360
References 362
Chapter 21. Dynamic Search in Graphs 364
Chapter 22. Dynamic Search in 
365 
REFERENCES 396
Chapter 23. A Leaf-Size Hierarchy of Two-Dimensional Alternating Turing Machines 402
1. Introduction 403
2. Preliminaries 403
3. Results 407
REFERENCES 416
CHAPTER 24. SIMPLE PROGRAMS WITH A FIXED NUMBER OF VARIABLES SEEM STILL HARD TO 
418 
1. Introduction 418
2. Definitions and Reduction Lemma 419
3. Simple programs with fixed number of variables 420
4. Remarks on time complexity 426
REFERENCES 428
Chapter 25. Theory of the Multiplicative Penalty Function Method for Linear Programming 430
1. Introduction 431
2. Problem 432
3. A Multiplicative Penalty Function and Its Derivatives 433
4. Algorithm 437
5. Convergence 439
6. Some Extensions 445
References 447
Chapter 26. Linear-time Computability of Combinatorial Problems on Generalized-Series-Parallel Graphs 450
1. Introduction and background 450
2. Generalized-series-parallel graphs 453
3. A linear-time maximum-cut algorithm for generalized-series-parallel graphs 458
4. The maximum cardinality of a minimal dominating set of a generalized-series-parallel graph 462
5. Concluding remarks and acknowledgements 467
6. References 468
Chapter 27. COMPETITIVE SNOOPY 
472 
1. INTRODUCTION 472
2. DEFINITIONS, NOTATION, AND MODELS 475
3. LOWER BOUNDS 479
4. DIRECT-MAPPED SNOOPY CACHING 481
5. ASSOCIATIVE CACHING 484
6. GENERAL SNOOPY CACHING 489
7. BLOCK SNOOPY CACHING 492
8. LIMITED BLOCK SNOOPY CACHING 493
9. REMARKS 496
ACKNOWLEDGEMENTS 496
PERSPECTIVES IN COMPUTING 497

Produkt-Details

• Erscheint lt. Verlag: 10.5.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik
• ISBN-10: 1-4832-7400-4 / 1483274004
• ISBN-13: 978-1-4832-7400-3 / 9781483274003