Computing and Combinatorics
Second Annual International Conference, COCOON '96, Hong Kong, June 17-19, 1996. Proceedings
Jin-Yi Cai, Chak Kuen Wong (Eds.)
Contents
Improved bounds for on-line load balancing - Matthew Andrews, Michel X. Goemans, Lisa Zhang - Pages 1-10
O(n log n)-average-time algorithm for shortest network under a given topology - Guoliang Xue, D. -Z. Du - Pages 11-20
Steiner problems on directed acyclic graphs - Tsan-sheng Hsu, Ku-Hui Tsai, Da-Wei Wang, D. T. Lee - Pages 21-30
Wormhole versus deflection routing: A case study on the mesh - Efstratios Karaivazoglou, Paul Spirakis, Vasilis Triantafilou - Pages 31-40
On sparse parity check matrices (extended abstract) - Hanno Lefmann, Pavel Pudlák, Petr Savický - Pages 41-49
Finding a hidden code by asking questions - Zhixiang Chen, Carlos Cunha, Steven Homer - Pages 50-55
Improved length lower bounds for reflecting sequences - H. K. Dai, K. E. Flannery - Pages 56-67
Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders - Hiroshi Imai, Satoru Iwata, Kyoko Sekine, Kensyu Yoshida - Pages 68-80
Output-sensitive reporting of disjoint paths (extended abstract) - Giuseppe Di Battista, Roberto Tamassia, Luca Vismara - Pages 81-91
Rectangular grid drawings of plane graphs - Saidur Rahman, Shin-ichi Nakano, Takao Nishizeki - Pages 92-105
Area-efficient algorithms for upward straight-line tree drawings - Chan-Su Shin, Sung Kwon Kim, Kyung-Yong Chwa - Pages 106-116
Straight skeletons for general polygonal figures in the plane - Oswin Aichholzer, Franz Aurenhammer - Pages 117-126
A note on uniform circuit lower bounds for the counting hierarchy (extended abstract) - Eric Allender - Pages 127-135
A note on the simulation of exponential threshold weights - Thomas Hofmeister - Pages 136-141
Harmonic analysis, real approximation, and the communication complexity of Boolean functions - Vince Grolmusz - Pages 142-151
Finding large planar subgraphs and large subgraphs of a given genus - Gruia Calinescu, Cristina G. Fernandes - Pages 152-161
Efficient deterministic algorithms for embedding graphs on books - Farhad Shahrokhi, Weiping Shi - Pages 162-168
Optimal bi-level augmentation for selective! enhancing graph connectivity with applications - Tsan-sheng Hsu, Ming-Yang Kao - Pages 169-178
Exact learning of subclasses of CDNF formulas with membership queries - Carlos Domingo - Pages 179-188
Fast separator decomposition for finite element meshes - Shang-Hua Teng - Pages 189-198
Reduction algorithms for constructing solutions in graphs with small treewidth - Hans L. Bodlaender, Babette de Fluiter - Pages 199-208
Fast RNC and NC algorithms for finding a maximal set of paths with an application - Ryuhei Uehara, Zhi-Zhong Chen, Xin He - Pages 209-218
Sparse suffix trees - Juha Kärkkäinen, Esko Ukkonen - Pages 219-230
Depth-efficient threshold circuits for multiplication and symmetric function computation - Chi-Hsiang Yeh, Emmanouel A. Varvarigos - Pages 231-240
A note on the self-witnessing property of computational problems - V. Arvind - Pages 241-249
The inverse satisfiability problem - Dimitris Kavvadias, Martha Sideri - Pages 250-259
The join can lower complexity - Lane A. Hemaspaandra, Zhigen Jiang, Jörg Rothe, Osamu Watanabe - Pages 260-267
On the distribution of eigenvalues of graphs - Xuerong Yong - Pages 268-272
On the difficulty of designing good classifiers - Michelangelo Grigni, Vincent Mirelli, Christos H. Papadimitriou - Pages 273-279
Approximating latin square extensions - S. Ravi Kumar, Alexander Russell, Ravi Sundaram - Pages 280-289
Approximating minimum keys and optimal substructure screens - Tatsuya Akutsu, Feng Bao - Pages 290-299
Reductions and convergence rates of average time - Jay Belanger, Jie Wang - Pages 300-309
On the complexity of computational problems associated with simple stochastic games - Akio Yanbe, Kouichi Sakurai - Pages 310-322
On the complexity of commutativity analysis - Oscar Ibarra, Pedro Diniz, Martin Rinard - Pages 323-332
Improved non-approximability results for vertex cover with density constraints - Andrea E. F. Clementi, Luca Trevisan - Pages 333-342
Some notes on the nearest neighbour interchange distance - Ming Li, John Tromp, Louxin Zhang - Pages 343-351
Distributed computing in asynchronous networks with byzantine edges - Vasant Shanbhogue, Moti Yung - Pages 352-360
Weight biased leftist trees and modified skip lists - Seonghun Cho, Sartaj Sahni - Pages 361-370
Probabilistic analysis of local search and NP-completeness result for constraint satisfaction - Hoong Chuin Lau - Pages 371-380
Two-guarding a rectilinear polygon - Xuehou Tan, Binhai Zhu - Pages 391-400
Three systems for shared generation of authenticators - R. Safavi-Naini - Pages 401-410
Efficient generation of elliptic curve cryptosystems - Kwok-Yan Lam, San Ling, Lucas C-K Hui - Pages 411-416
Superconnectivity for minimal multi-loop networks - Jixiang Meng - Pages 417-419
Springer, Lecture Notes in Computer Science - Volume 1090, Paperback, english, 419 pages
