Recent Advances in Algorithmic Combinatorics

by Reed, Bruce A.; Linhares-Sales, Claudia; Sales, Claudia L.

• ISBN13: 9780387954349
• ISBN10: 0387954341
• Format: Hardcover
• Copyright: 2003-01-01
• Publisher: Springer Nature

Summary

Combinatorics is one of the fastest growing fields of mathematics. One reason for this is because manypractical problems can be modeled and then efficiently solved using combinator combinatorial theory. This real worldmotivation for studying algorithmic combinatorics has led not only to the development of many software packages but also to some beautiful mathematics which has no direct application to applied problems. This book highlights a few of the exciting recent developments in algorithmic combinatorics, including the search for patterns in DNA and protein sequences, the theory of semi-definite programming and its role in combinatorial optimization, and the algorithmic aspects of tree decompositions and it's applications to thetheory of databases, code optimization, and bioinformatics.Claudia Linhares-Sales is Assistant Professor of Computer Science at the Federal University of Cearß, Brazil. Bruce Reed is Canada Research Chair in Graph Theory at the School of of Computer Science of McGill University.

Table of Contents

Preface	v
List of Contributors	xiii
The Matching Lattice	1	(26)
M. H. de Carvalho
C.L. Lucchesi
U.S.R. Murty
Perfect Matchings	1	(1)
Matching Covered Graphs	2	(1)
The Matching Lattice	3	(2)
Tight Cut Decompositions	5	(5)
Separating Cut Decompositions	10	(4)
Removable Edges	14	(2)
Ear Decompositions	16	(4)
Optimal Ear Decomposition	20	(1)
A Characterization of the Matching Lattice	21	(2)
Unsolved Problems	23	(4)
References	24	(3)
Discrete Mathematics and Radio Channel Assignment	27	(38)
C. McDiarmid
Introduction	27	(1)
The constraint matrix model	28	(1)
General results for the constraint matrix model	29	(9)
How hard is channel assignment?	38	(2)
Channel assignment in the plane	40	(7)
Channel assignment with demands	47	(5)
Random channel assignment problems	52	(4)
Modelling radio channel assignment	56	(9)
References	58	(7)
On the coloration of perfect graphs	65	(20)
F. Maffray
Introduction	65	(1)
Basic definitions and notation	66	(1)
Bounds on the chromatic number	67	(1)
Edge coloring	68	(1)
Sequential Algorithms	69	(2)
Sequential coloring with bichromatic exchange	71	(3)
Sequential coloring with trichromatic exchange	74	(1)
Coloring by contraction	74	(5)
Other methods	79	(6)
References	80	(5)
Algorithmic Aspects of Tree Width	85	(24)
B. A. Reed
Dividing and Conquering	85	(4)
Tree decompositions and tree width	89	(5)
Finding Bounded Width Decompositions	94	(3)
Using Bounded Width Decompositions	97	(1)
Walls	98	(3)
Some Applications	101	(8)
References	104	(5)
A Survey on Clique Graphs	109	(28)
J. L. Szwarcfiter
Introduction	109	(1)
Operations on Clique Graphs	110	(1)
A General Characterization	111	(2)
Clique Graphs of Classes of Graphs	113	(2)
Clique Inverse Classes	115	(5)
Iterated Clique Graphs	120	(1)
Convergence and Divergence	121	(4)
Diameters	125	(3)
Remarks and Problems	128	(9)
References	130	(7)
Semidefinite Programs and Combinatorial Optimization	137	(58)
L. Lovasz
Introduction	137	(5)
Preliminaries	142	(9)
Semidefinite programs	151	(7)
Obtaining semidefinite programs	158	(8)
Semidefinite programming in proofs	166	(7)
Semidefinite programming in approximation algorithms	173	(4)
Constraint generation and quadratic inequalities	177	(6)
Extensions and problems	183	(12)
References	189	(6)
Approximability of NP-Optimization Problems	195	(50)
A. Steger
Introduction	195	(10)
Proving Lower Bounds	205	(7)
A Hierarchy for NP-Optimization Problems	212	(8)
Constructing Reductions	220	(19)
Open Problems	239	(6)
References	239	(6)
Pattern Inference under many Guises	245	(44)
M.-F. Sagot
Y. Wakabayashi
Introduction	245	(1)
Biological motivation	246	(1)
Notions of similarity	247	(10)
Models and their properties	257	(3)
Algorithms	260	(29)
References	284	(5)
Szemeredi's Regularity Lemma and Quasi-randomness	289	(58)
Y. Kohayakawa
V. Rodl
Introduction	289	(3)
The regularity lemma	292	(6)
An application of the regularity lemma	298	(13)
Further applications	311	(5)
Proof of the regularity lemma	316	(8)
Local conditions for regularity	324	(7)
A new quasi-random property	331	(16)
References	347