Discrete Algorithms and Complexity. Proceedings of the Japan–US Joint Seminar, June 4–6, 1986, Kyoto, Japan

Content: 
PERSPECTIVES IN COMPUTING, Vol. 15, Page ii
Front Matter, Page iii
Copyright, Page iv
Contributors, Pages vii-ix
Foreword, Page xi, David S. Johnson, Takao Nishizeki, Akihiro Nozaki, Herbert S. Wilf
An Upper Bound on the Expected Cost of an Optimal Assignment, Pages 1-4, Richard M. Karp
The Principal Partition of Vertex-Weighted Graphs and Its Applications, Pages 5-33, Takao Ozawa, Yoji Kajitani, Shuichi Ueno
Generalized Colorings, Pages 35-49, Michael O. Albertson
Voronoi Diagram for Points in a Simple Polygon, Pages 51-64, Takao Asano, Tetsuo Asano
Computing the Geodesic Center of a Simple Polygon, Pages 65-79, Tetsuo Asano, Godfried Toussaint
On deleting vertices to make a graph of positive genus planar, Pages 81-98, Joan P. Hutchinson, Gary L. Miller
Algorithms for Routing around a Rectangle: Extended Abstract, Pages 99-105, Hitoshi Suzuki, Takao Nishizeki, Nobuji Saito
A Remark on the Complexity of the Knapsack Problem, Pages 107-118, Hajime Machida
Fast, Rigorous Factorization and Discrete Logarithm Algorithms, Pages 119-143, Carl Pomerance
Redundant Coding for Local Computability, Pages 145-159, Hiroto Yasuura, Naofumi Takagi, Shuzo Yajima
SOME PROPERTIES OF THE PARALLEL BUBBLING AND PARALLEL SORTS ON A MESH–CONNECTED PROCESSOR ARRAY, Pages 161-183, Kazuhiro SADO, Yoshihide IGARASHI
Game Solving Procedure H* Is Unsurpassed, Pages 185-200, T. Ibaraki
Algorithmic Problems in Modeling and Electronic Prototyping, Pages 201-222, John Hopcroft
Complementary Approaches to CNF Boolean Equations, Pages 223-236, Kazuo Iwama
Open Problems in Number Theoretic Complexity, Pages 237-262, Leonard M. Adleman, Kevin S. McCurley
Decision Problem of the Security for Cryptographic Protocols, Pages 263-286, Toru FUJIWARA, Kenichi TANIGUCHI, Tadao KASAMI
A Digital Signature Scheme Secure Against Adaptive Chosen Message Attack: Extended Abstract, Pages 287-310, Shafi Goldwasser, Silvio Micali, Ronald L. Rivest
Are problems having a polynomial time upper bound actually thought to be feasible?, Pages 311-324, Akeo ADACHI, Takumi KASAI
On Probability that a Randomly Selected Set Has Some complexity-Theoretical Property, Pages 325-339, Kojiro Kobayashi
Ranking Rooted Trees, and a Graceful Application, Pages 341-349, Herbert S. Wilf, Nancy A. Yoshimura
Dynamic Search in Graphs, Pages 351-387, F.R.K. Chung, R.L. Graham, M.E. Saks
A Leaf-Size Hierarchy of Two-Dimensional Alternating Turing Machines, Pages 389-404, Katsushi Inoue, Itsuo Takanami, Juraj Hromkovič
SIMPLE PROGRAMS WITH A FIXED NUMBER OF VARIABLES SEEM STILL HARD TO ANALYZE, Pages 405-416, Shigeki Iwata, Takumi Kasai
Theory of the Multiplicative Penalty Function Method for Linear Programming, Pages 417-435, Masao IRI, Hiroshi IMAI
Linear-time Computability of Combinatorial Problems on Generalized-Series-Parallel Graphs, Pages 437-457, E. Hare, S. Hedetniemi, R. Laskar, K. Peters, T. Wimer
COMPETITIVE SNOOPY CACHING, Pages 459-483, Anna R. Karlin, Mark S. Manasse, Larry Rudolph, Daniel D. Sleator
PERSPECTIVES IN COMPUTING, Page ibc1