Ebook: Combinatorics and Computer Science: 8th Franco-Japanese and 4th Franco-Chinese Conference Brest, France, July 3–5, 1995 Selected Papers

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.

---

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.

---

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.
Content:
Front Matter....Pages -
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 ?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
Back Matter....Pages -

---

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.
Content:
Front Matter....Pages -
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 ?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
Back Matter....Pages -
....