Computing and Combinatorics

1. Front Matter

   PDF

2. The complexity of mean payoff games

   • Uri Zwick, Michael S. Paterson

   Pages 1-10

3. Approximation of coNP sets by NP-complete sets

   • Kazuo Iwama, Shuichi Miyazaki

   Pages 11-20

4. How to draw a planar clustered graph

   • Qing -Wen Feng, Robert F. Cohen, Peter Eades

   Pages 21-30

5. An efficient orthogonal grid drawing algorithm for cubic graphs

   • Tiziana Calamoneri, Rossella Petreschi

   Pages 31-40

6. Constrained independence system and triangulations of planar point sets

   • Siu-Wing Chengl, Yin-Feng Xu

   Pages 41-50

7. Three dimensional weak visibility: Complexity and applications

   • Caoan Wang, Binhai Zhu

   Pages 51-60

8. Rectangulating rectilinear polygons in parallel

   • Sung Kwon Kim

   Pages 61-70

9. Efficient randomized incremental algorithm for the closest pair problem using Leafary trees

   • V. Kamakoti, Kamala Krithivasan, C. Pandu Rangan

   Pages 71-80

10. Testing containment of object-oriented conjunctive queries is ∏ 2 p -hard

    • Edward P. F. Chan, Ron van der Meyden

    Pages 81-90

11. Computing infinite relations using finite expressions: A new approach to the safety issue in relational databases

    • Ruogu Zhang

    Pages 91-100

12. Set-term unification in a logic database language

    • Seung Jin Lim, Yiu-Kai Ng

    Pages 101-110

13. Computations with finite closure systems and implications

    • Marcel Wild

    Pages 111-120

14. Maximum tree-packing in time O(n^5/2)

    • Andrzej Lingas

    Pages 121-130

15. Optimal algorithms for finding connected components of an unknown graph

    • Weiping Shi, Douglas B. West

    Pages 131-140

16. The multi-weighted spanning tree problem

    • Joseph L. Ganley, Mordecai J. Golin, Jeffrey S. Salowe

    Pages 141-150

17. Algorithmic graph embeddings

    • Jianer Chen

    Pages 151-160

18. Analysis of quorum-based protocols for distributed (k+1)-exclusion

    • Divyakant Agrawal, Ömer Eğecioğlu, Amr El Abbadi

    Pages 161-170

19. A highly fault-tolerant quorum consensus method for managing replicated data

    • Xuemin Lin, Maria E. Orlowska

    Pages 171-180

20. Constructing Craig interpolation formulas

    • Guoxiang Huang

    Pages 181-190

This book constitutes the proceedings of the First Annual International Conference on Computing and Combinatorics, COCOON '95, held in Xi'an, China in August 1995.
The 52 thoroughly refereed full papers and the 22 short presentations included in this volume were selected from a total of 120 submissions. All current aspects of theoretical computer science and combinatorial mathematics related to computing are addressed; in particular, there are sections on complexity theory, graph drawing, computational geometry, databases, graph algorithms, distributed programming and logic, combinatorics, machine models, combinatorial designs, algorithmic learning, algorithms, distributed computing, and scheduling.

• Combinatorics
• Erfüllbarkeitsproblem der Aussagenlogik
• Layout
• algorithm
• algorithms
• automata
• complexity
• complexity theory
• computational geometry
• data structure
• distributed computing
• distributed programming
• logic
• optimization
• programming
• algorithm analysis and problem complexity

Policies and ethics