1. COCOON 1995: Xi'an, China

Ding-Zhu Du, Ming Li (Eds.): Computing and Combinatorics, First Annual International Conference, COCOON '95, Xi'an, China, August 24-26, 1995, Proceedings. Lecture Notes in Computer Science 959 Springer 1995, ISBN 3-540-60216-X BibTeX

@proceedings{DBLP:conf/cocoon/1995,
  editor    = {Ding-Zhu Du and
               Ming Li},
  title     = {Computing and Combinatorics, First Annual International Conference,
               COCOON '95, Xi'an, China, August 24-26, 1995, Proceedings},
  booktitle = {COCOON},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {959},
  year      = {1995},
  isbn      = {3-540-60216-X},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Complexity Theory

Uri Zwick, Mike Paterson: The Complexity of Mean Payoff Games. 1-10 BibTeX
Kazuo Iwama, Shuichi Miyazaki: Approximation of coNP Sets by NP-complete Sets. 11-20 BibTeX

Graph Drawing

Qing-Wen Feng, Robert F. Cohen, Peter Eades: How to Draw a Planar Clustered Graph. 21-30 BibTeX
Tiziana Calamoneri, Rossella Petreschi: An Efficient Orthogonal Grid Drawing Algorithm For Cubic Graphs. 31-40 BibTeX

Computational Geometry

Siu-Wing Cheng, Yin-Feng Xu: Constrained Independence System and Triangulations of Planar Point Sets. 41-50 BibTeX
Cao An Wang, Binhai Zhu: Three Dimensional Weak Visibility: Complexity and Applications. 51-60 BibTeX
Sung Kwon Kim: Rectangulating Rectilinear Polygons in Parallel. 61-70 BibTeX
V. Kamakoti, Kamala Krithivasan, C. Pandu Rangan: Efficient Randomized Incremental Algorithm For The Closest Pair Problem Using Leafary Trees. 71-80 BibTeX

Database

Edward P. F. Chan, Ron van der Meyden: Testing Containment of Object-Oriented Conjunctive Queries is Pi_2^p-hard. 81-90 BibTeX
Ruogu Zhang: Computing Infinite Relations Using Finite Expressions: A New Approach To The Safety Issue In Relational Databases. 91-100 BibTeX
Seung Jin Lim, Yiu-Kai Ng: Set-Term Unification in a Logic Database Language. 101-110 BibTeX
Marcel Wild: Computations with Finite Closure Systems and Implications. 111-120 BibTeX

Graph Algorithms

Andrzej Lingas: Maximum Tree-Packing in Time O(n^5/2). 121-130 BibTeX
Weiping Shi, Douglas B. West: Optimal Algorithms for Finding Connected Components of an Unknown Graph. 131-140 BibTeX
Joseph L. Ganley, Mordecai J. Golin, Jeffrey S. Salowe: The Multi-Weighted Spanning Tree Problem (Extended Abstract). 141-150 BibTeX
Jianer Chen: Algorithmic Graph Embeddings (Extended Abstract). 151-160 BibTeX

Distributed/Logic

Divyakant Agrawal, Ömer Egecioglu, Amr El Abbadi: Analysis of Quorum-Based Protocols for Distributed (k+1)-Exclusion. 161-170 BibTeX
Xuemin Lin, Maria E. Orlowska: A Highly Fault-Tolerant Quorum Consensus Method for Managing Replicated Data. 171-180 BibTeX
Guoxiang Huang: Constructing Craig Interpolation Formulas. 181-190 BibTeX
Yoshinobu Kawabe, Naohiro Ishii: Currying of Order-Sorted Term Rewriting Systems. 191-202 BibTeX

Graph Algorithms

S. Rengarajan, C. E. Veni Madhavan: Stack and Queue Number of 2-Trees. 203-212 BibTeX
Scott K. Walley, Harry H. Tan: Shortest Paths in Random Weighted Graphs. 213-222 BibTeX
Xiao Zhou, Takao Nishizeki: Simple Reduction of f-Colorings to Edge-Colorings. 223-228 BibTeX
Kazuyoshi Hayase, Kunihiko Sadakane, Seiichiro Tani: Output-size Sensitiveness of OBDD Construction Through Maximal Independent Set Problem. 229-234 BibTeX

Combinatorics

John Tromp, Louxin Zhang, Ying Zhao: Small Weight Bases for Hamming Codes. 235-243 BibTeX
Julien Cassaigne, Juhani Karhumäki: Toeplitz Words, Generalized Periodicity and Periodically Iterated Morphisms (Extended Abstract). 244-253 BibTeX
Elena Barcucci, Alberto Del Lungo, Elisa Pergola, Renzo Pinzani: A Construction for Enumerating k-coloured Motzkin Paths. 254-263 BibTeX
Vladimir A. Oleshchuk: On Public-Key Cryptosystem Based on Church-Rosser String-Rewriting Systems (Extended Abstract). 264-269 BibTeX

Machine Models

John E. Savage: Extending the Hong-Kung Model to Memory Hierarchies. 270-281 BibTeX
Liming Cai, Jianer Chen: On log-Time Alternating Turing Machines of Alternation Depth k (Extended Abstract). 282-291 BibTeX

Combinatorial Designs

Kaoru Kurosawa, Sanpei Kageyama: New Bound for Afine Resolvable Designs and Its Application to Authentication Codes. 292-302 BibTeX
Boris D. Lubachevsky, Ronald L. Graham: Dense Packings of 3k(k+1)+1 Equal Disks in a Circle for k=1, 2, 3, 4 and 5. 303-312 BibTeX

Parallel Algorithms/Learning

Josep Díaz, Alan Gibbons, Grammati E. Pantziou, Maria J. Serna, Paul G. Spirakis, Jacobo Torán: Efficient Parallel Algorithms for some Tree Layout Problems. 313-323 BibTeX
Yijie Han, Xiaojun Shen: Conservative Algorithms for Parallel and Sequential Integer Sorting. 324-333 BibTeX
Zhixiang Chen: An Optimal Algorithm for Proper Learning of Unions of Two Rectangles with Queries. 334-343 BibTeX
Zhixiang Chen: Disjunctions of Negated Counting Functions Are Efficiently Learnable with Equivalence Queries. 344-349 BibTeX

Combinatorics

Shiquan Wu: Non-empty Cross-3-Intersection Theorems of Subsets. 350-356 BibTeX
Bo Yu: Convexity of Minimal Total Dominating Functions in Graphs. 357-365 BibTeX
Jean Hardouin Duparc, Philippe Rolland: Transformations for Maximal Planar Graphs with Minimum Degree Five. 366-371 BibTeX
You Zhaoyong, Wang Chuanglong: An Asynchrolous Parallel Method for Linaer Systems. 372-378 BibTeX

Combinatorics

Zhang Xiangde: On a Kind of Sequence of Polynomials. 379-383 BibTeX
Jixiang Meng: Hamiltonian Cycles in 2-generated Cayley Digraphs of Abelian Groups. 384-387 BibTeX
Cheng-Xu Xu, Zhun-Wei Lu: Pandiagonal Magic Squares. 388-391 BibTeX
Hua Wang, Zhao-yong You: PFFM and Quasi-Morishima Matrices. 392-395 BibTeX
C. F. Chang, J. X. Chang, X. C. Lu, Peter Che Bor Lam, J. F. Wang: Edge-Face Total Chromatic Number of Outerplanar Graphs with Delta(G)=6. 396-399 BibTeX

Complexity Theory

Rainer Schuler, Tomoyuki Yamakami: Sets Computable in Polynomial Time on Average. 400-409 BibTeX
Jay Belanger, Jie Wang: Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions. 410-419 BibTeX
Kojiro Kabayashi: Transformations that Preserve Maligness of Universal Distributions. 420-429 BibTeX
Lane A. Hemaspaandra, Jörg Rothe: Intersection Suffices for Boolean Hierarchy Equivalence. 430-435 BibTeX

Algorithms

Dean Kelley, Peng-Jun Wan, Quifan Yang: A 3/2 log3-Competive Algorithm for the Counterfeit Cain Problem. 436-445 BibTeX
Svante Carlsson, Jingsen Chen: Searching Rigid Data Structures (Extended Abstract). 446-451 BibTeX
Bo-Ting Yang: A Better Subgraph of the Minimum Weight Triangulation. 452-455 BibTeX
Wen Gao, Baocai Yin: Sequence Decomposition Method for Computing a Gröbner Basis and Its Application to Bivariate Spline. 456-461 BibTeX

Distributed Computing

Leqiang Bai, Peter M. Yamakawa, Hiroyuki Ebara, Hideo Nakando: A Broadcasting Algorithm on the Arrangement Graph. 462-471 BibTeX
Shyue-Horng Shiau, Chang-Biau Yang: A Fast Maximum Finding Algorithm on Broadcast Communication. 472-481 BibTeX
Aditya Shastri: Broadcasting in General Networks I: Trees. 482-489 BibTeX
Shyh-Chain Chern, Tai-Ching Tuan, Jung-Sing Jwo: Uni-directional Alternating Group Graphs. 490-495 BibTeX

Complexity Theory

Kouichi Sakurai: On Separating Proofs of Knowledge from Proofs of Membership of Languages and Its Application to Secure Identification Schemes (Extended Abstract). 496-509 BibTeX
Sven Oliver Krumke, Hartmut Noltemeier, S. S. Ravi, Madhav V. Marathe: Compact Location Problems with Budget and Communication Constraints. 510-519 BibTeX

Algorithms

Siu-Wing Cheng, Michael Kaminski, Shmuel Zaks: Minimum Dominating Sets of Intervals on Lines (Extended Abstract). 520-529 BibTeX
Ying Choi, Tak Wah Lam: Two-Dimensional Pattern Matching on a Dynamic Library of Texts. 530-538 BibTeX

Complexity Theory

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan: Structure in Approximation Classes (Extended Abstract). 539-548 BibTeX
Marcus Peinado: Improved Lower Bounds for the Randomized Boppana-Halldórsson Algorithm for MAXCLIQUE. 549-558 BibTeX
Qi Cheng, Hong Zhu: MNP: A Class of NP Optimization Problems (Extended Abstract). 559-565 BibTeX
Roman Bacik, Sanjeev Mahajan: Semidefinite Programming and its Applications to NP Problems. 566-575 BibTeX

Algorithms

Lucas Chi Kwong Hui, Kwok-Yan Lam: Analysis and Experimentation on List Update Algorithms. 576-581 BibTeX
B. N. Khoury, Panos M. Pardalos: An Exact Branch and Bound Algorithm for the Steiner Problem in Graphs. 582-590 BibTeX
Huang Wenqui, Li Wei, Lu Weifeng, Zhang Yuping: A Physical Model for the Satisfiability Problem. 591-596 BibTeX
Sam M. Kim, Robert McNaughton: An Efficient Algorithm for Local Testability Problem of Finite State Automata. 597-606 BibTeX

Scheduling

Xiangdong Yu, Moti Yung: Scheduling Task-Tree with Additive Scales on Parallel / Distributed Machines. 607-616 BibTeX
Chi-lok Chan, Gilbert H. Young: Single-vehicle Scheduling Problem on a Straight Line with Time Window Constraints. 617-626 BibTeX
Rongheng Li, Lijie Shi: An On-Line Algorithm for Some Uniform Processor Scheduling. 627-632 BibTeX
Peter Jeavons, David A. Cohen: An Algebraic Characterization of Tractable Constraints. 633-642 BibTeX
Jiyu Ding, Chngxiang Qing, Guodong Song: Limit Property of Unbalanced Development in Economic Network. 643-646 BibTeX

Plenary Survey Lectures

Derick Wood: Document Processing, Theory, and Practice (Abstract). 647 BibTeX
Tao Jiang: Matching and Comparing Sequences in Molecular Biology (Abstract). 648-649 BibTeX
Vijay V. Vazirani: Primal-Dual Schema Based Approximation Algorithms (Abstract). 650-652 BibTeX