Combinatorics and Computer Science

1. Front Matter

   PDF

2. Equitable and m-bounded coloring of split graphs

   • Bor-Liang Chen, Ming-Tat Ko, Ko-Wei Lih

   Pages 1-5

3. Four coloring for a subset of maximal planar graphs with minimum degree five

   • Philippe Rolland

   Pages 6-17

4. Enumeration algorithm for the edge coloring problem on bipartite graphs

   • Yasuko Matsui, Tomomi Matsui

   Pages 18-26

5. On-line recognition of interval graphs in O(m+nlog n) time

   • Wen-Lian Hsu

   Pages 27-38

6. Connected proper interval graphs and the guard problem in spiral polygons

   • Chiuyuan Chen, Chin-Chen Chang

   Pages 39-47

7. Weighted connected domination and Steiner trees in distance-hereditary graphs

   • Hong-Gwa Yeh, Gerard J. Chang

   Pages 48-52

8. On central spanning trees of a graph

   • S. Bezrukov, F. Kaderali, W. Poguntke

   Pages 53-57

9. Complete bipartite decompositions of crowns, with applications to complete directed graphs

   • Chiang Lin, Jenq-Jong Lin, Tay-Woei Shyu

   Pages 58-66

10. Finding an antidirected Hamiltonian path starting with a forward arc from a given vertex of a tournament

    • E. Bampis, P. Hell, Y. Manoussakis, M. Rosenfeld

    Pages 67-73

11. Complementary ℓ1-graphs and related combinatorial structures

    • Michel Deza, Tayuan Huang

    Pages 74-90

12. Double description method revisited

    • Komei Fukuda, Alain Prodon

    Pages 91-111

13. On skeletons, diameters and volumes of metric polyhedra

    • Antoine Deza, Michel Deza, Komei Fukuda

    Pages 112-128

14. Improving branch and bound for Jobshop scheduling with constraint propagation

    • Yves Caseau, François Laburthe

    Pages 129-149

15. A new efficiently solvable special case of the three-dimensional axial bottleneck assignment problem

    • Bettina Klinz, Gerhard J. Woeginger

    Pages 150-162

16. Ramsey numbers by stochastic algorithms with new heuristics

    • Jihad Jaam

    Pages 163-181

17. On the hybrid neural network model for solving optimization problems

    • Fouad B. Chedid

    Pages 182-193

18. Constructive — non-constructive approximation and maximum independent set problem

    • Marc Demange, Vangelis Th. Paschos

    Pages 194-207

19. Weakly greedy algorithm and pair-delta-matroids

    • Takashi Takabatake

    Pages 208-217

20. On integer multiflows and metric packings in matroids

    • Karina Marcus, András Sebő

    Pages 218-233

This book presents a collection of 33 strictly refereed full papers on combinatorics and computer science; these papers have been selected from the 54 papers accepted for presentation at the joint 8th Franco-Japanese and 4th Franco-Chinese Conference on Combinatorics in Computer Science, CCS '96, held in Brest, France in July 1995.
The papers included in the book have been contributed by authors from 10 countries; they are organized in sections entitled graph theory, combinatorial optimization, selected topics, and parallel and distributed computing.

• Graph
• Graph theory
• combinatorial optimization
• computer
• computer science
• distributed computing
• optimization

Policies and ethics