Combinatorics and Computer Science: 8th Franco-Japanese and 4th Franco-Chinese Conference, Brest, France, July 3 - 5, 1995 Selected Papers (Lecture Notes in Computer Science (1120))

"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."--PUBLISHER'S WEBSITE Equitable and m -bounded coloring of split graphs....Pages 1-5 Four coloring for a subset of maximal planar graphs with minimum degree five....Pages 6-17 Enumeration algorithm for the edge coloring problem on bipartite graphs....Pages 18-26 On-line recognition of interval graphs in O (m+nlog n) time....Pages 27-38 Connected proper interval graphs and the guard problem in spiral polygons....Pages 39-47 Weighted connected domination and Steiner trees in distance-hereditary graphs....Pages 48-52 On central spanning trees of a graph....Pages 53-57 Complete bipartite decompositions of crowns, with applications to complete directed graphs....Pages 58-66 Finding an antidirected Hamiltonian path starting with a forward arc from a given vertex of a tournament....Pages 67-73 Complementary l 1 -graphs and related combinatorial structures....Pages 74-90 Double description method revisited....Pages 91-111 On skeletons, diameters and volumes of metric polyhedra....Pages 112-128 Improving branch and bound for Jobshop scheduling with constraint propagation....Pages 129-149 A new efficiently solvable special case of the three-dimensional axial bottleneck assignment problem....Pages 150-162 Ramsey numbers by stochastic algorithms with new heuristics....Pages 163-181 On the hybrid neural network model for solving optimization problems....Pages 182-193 Constructive — non-constructive approximation and maximum independent set problem....Pages 194-207 Weakly greedy algorithm and pair-delta-matroids....Pages 208-217 On integer multiflows and metric packings in matroids....Pages 218-233 Optimum alphabetic binary trees....Pages 234-243 Block codes for dyadic phase shift keying....Pages 244-262 Zigzag codes and z -free hulls....Pages 263-274 Contiguity orders....Pages 275-287 Worst-case analysis for on-line data compression....Pages 288-300 Gossiping in cayley graphs by packets....Pages 301-315 On embedding 2-dimensional toroidal grids into de Bruijn graphs with clocked congestion one....Pages 316-327 N-cube string matching algorithm with long texts....Pages 328-340 Combinatorics for multiprocessor scheduling optimization and other contexts in computer architecture....Pages 341-347 Some applications of combinatorial optimization in parallel computing....Pages 348-366 On the parallel complexity of the alternating Hamiltonian cycle problem....Pages 367-377 Threshold graphs and synchronization protocols....Pages 378-395 Task assignment in distributed systems using network flow methods....Pages 396-405 Distributed rerouting in DCS mesh networks....Pages 406-415

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.