Recent Advances in Algorithms and Combinatorics [Reed & Sales 2002-11-22].pdf

(1575 KB) Pobierz
Editors-in-Chief
´
Redacteurs-en-chef
Jonathan Borwein
Peter Borwein
1
2
3
4
5
6
7
8
9
10
11
ˇ
ˇ
ˇ
H
ERMAN
/K
UCERA
/S
IMSA
Equations and Inequalities
A
RNOLD
Abelian Groups and Representations of Finite Partially Ordered Sets
B
ORWEIN
/L
EWIS
Convex Analysis and Nonlinear Optimization
L
EVIN
/L
UBINSKY
Orthogonal Polynomials for Exponential Weights
K
ANE
Reflection Groups and Invariant Theory
P
HILLIPS
Two Millennia of Mathematics
D
EUTSCH
Best Approximations in Inner Product Spaces
F
ABIAN ET AL
. Functional Analysis and Infinite-Dimensional Geometry
ˇIˇ
K
R
´
ZEK
/L
UCA
/S
OMER
17 Lectures on Fermat Numbers
B
ORWEIN
Computational Excursions in Analysis and Number Theory
R
EED
/S
ALES
Recent Advances in Algorithms and Combinatorics
Bruce A. Reed
Editors
´
Claudia L. Sales
Recent Advances in
Algorithms and
Combinatorics
With 52 Illustrations
Bruce A. Reed
Equipe Combinatoire
CNRS, Paris, France
and
McGill University
Montreal Canada
´
Claudia L. Sales
Universidade Federal do Ceara
Departamento de Computacao—LIA
Campus do Pici—Bloco 910
CEP 60455-760 Fortaleza-CE Brasil
linhares@lia.ufc.br
Editors-in-Chief
´
Redacteurs-en-chef
Jonathan Borwein
Peter Borwein
Centre for Experimental and Constructive Mathematics
Department of Mathematics and Statistics
Simon Fraser University
Burnaby, British Columbia V5A 1S6
Canada
cbs-editors@cms.math.ca
Mathematics Subject Classification (2000): 05-06
Library of Congress Cataloging-in-Publication Data
´
Recent advances in algorithms and combinatorics / Bruce Reed, Claudia L. Sales.
p. cm. — (CMS books in mathematics ; 11)
Includes bibliographical references.
ISBN 0-387-95434-1 (alk. paper)
´
1. Combinatorial analysis. I. Reed, Bruce A. II. L. Sales, Claudia. III. Series.
QA164 .R395 2002
511′6—dc21
2002017379
ISBN 0-387-95434-1
Printed on acid-free paper.
2003 Springer-Verlag New York, Inc.
All rights reserved. This work may not be translated or copied in whole or in part without the
written permission of the publisher (Springer-Verlag New York, Inc., 175 Fifth Avenue, New York,
NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use
in connection with any form of information storage and retrieval, electronic adaptation, computer
software, or by similar or dissimilar methodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if
they are not identified as such, is not to be taken as an expression of opinion as to whether or not
they are subject to proprietary rights.
Printed in the United States of America.
9 8 7 6 5 4 3 2 1
SPIN 10864587
Typesetting: Pages created by the authors using a Springer TEX macro package.
www.springer-ny.com
Springer-Verlag New York Berlin Heidelberg
A member of BertelsmannSpringer Science+Business Media GmbH
Preface
Combinatorics is one of the fastest growing fields of mathematics. In large
measure this is because many practical problems can be modeled and then
efficiently solved using combinatorial theory. This real world motivation 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. In this volume we highlight some
exciting recent developments in algorithmic combinatorics.
Most practical applications of algorithmic combinatorics would be im-
possible without the use of the computer. As computers become ever more
powerful, more and more applications become possible. Computational
biology is one example of a relatively new field in which algorithmic com-
binatorics plays a key role. The chapter by Sagot and Wakabayashi in this
volume discusses how combinatorial tools can be used to search for patterns
in DNA and protein sequences.
The information technology revolution has not only allowed for the res-
olution of practical problems using combinatorial techniques, it has also
been the source of many new combinatorial problems. One example is ra-
dio channel assignment. In this problem we have a number of transmitters
each of which must handle a number of calls. Each call must be assigned a
frequency in such a way that interference is avoided (thus calls handled by
the same transmitter are assigned different frequencies as are calls handled
by transmitters which are
near
each other). The explosive growth in the
use of the frequency spectrum due to, e.g., mobile telephone networks, has
made it a very valuable resource. Indeed spectrum licenses were sold for
billions of dollars in recent actions. So, efficiently assigning radio channels
is of great importance. In his chapter in this volume, McDiarmid describes
how to model radio channel assignment as a graph colouring problem and
surveys the results that have been obtained using this approach.
Using graph colouring models to aid in studying how to direct the flow
of information through transmission channels is not new. Shannon defined
the zero-error capacity of a noisy (memoryless) channel as the maximum
number of bits per symbol which could be sent through the channel whilst
avoiding the introduction of errors. In 1961, Berge noted that determining
the Shannon capacity of a channel could be modeled as a graph theory

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin