Digraphs_ Theory, Algorithms and Applications (2nd ed.) [Bang-Jensen & Gutin 2010-09-28].pdf

(6612 KB) Pobierz
Springer Monographs
in
Mathematics
For further volumes:
www.springer.com/series/3733
Jørgen Bang-Jensen
r
Gregory Z. Gutin
Digraphs
Theory, Algorithms and Applications
Second edition
Prof. Jørgen Bang-Jensen
University of Southern Denmark
Dept. Mathematics & Computer Science
Campusvej 55
5230 Odense
Denmark
jbj@imada.sdu.dk
Prof. Gregory Z. Gutin
Royal Holloway Univ. London
Dept. Computer Science
Egham Hill
Egham, Surrey
United Kingdom TW20 0EX
gutin@cs.rhul.ac.uk
ISSN 1439-7382
ISBN 978-1-84800-997-4 (hardcover)
e-ISBN 978-1-84800-998-1
ISBN 978-0-85729-041-0 (softcover)
DOI 10.1007/978-1-84800-998-1
Springer London Dordrecht Heidelberg New York
British Library Cataloguing in Publication Data
A catalogue record for this book is available from the British Library
Library of Congress Control Number: 2008939033
Mathematics Subject Classification (2000): 05C20, 05C38, 05C40, 05C45, 05C70, 05C85, 05C90, 05C99,
68R10, 68Q25, 68W05, 68W40, 90B06, 90B70, 90C35, 94C15
© Springer-Verlag London Limited 2001, 2009, First softcover printing 2010
Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permit-
ted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored
or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in
the case of reprographic reproduction in accordance with the terms of licenses issued by the Copyright
Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to the publishers.
The use of registered names, trademarks, etc., in this publication does not imply, even in the absence of a
specific statement, that such names are exempt from the relevant laws and regulations and therefore free
for general use.
The publisher makes no representation, express or implied, with regard to the accuracy of the information
contained in this book and cannot accept any legal responsibility or liability for any errors or omissions
that may be made.
Cover design:
deblik
Printed on acid-free paper
Springer is part of Springer Science+Business Media (www.springer.com)
To Lene and Irina
Preface to the Second Edition
The theory of graphs can be roughly partitioned into two branches: the areas
of undirected graphs and directed graphs (digraphs). While there are many
books on undirected graphs with new ones coming out regularly, the first
edition of
Digraphs,
which was published in 2000, is the only modern book
on graph theory covering more than a small fraction of the theory of directed
graphs.
Since we wrote the first edition, the theory of directed graphs has contin-
ued to evolve at a high speed; many important results, including some of the
conjectures from the first edition, have been proved and new methods were
developed. Hence a new completely revised version became necessary. Instead
of merely adding some new results and deleting a number of old ones, we took
the opportunity to reorganize the book and increase the number of chapters
from 12 to 18. This allows us to treat, in separate chapters, important topics
such as branchings, feedback arc and vertex sets, connectivity augmenta-
tions, sparse subdigraphs with prescribed connectivity, applications, as well
as packing, covering and decompositions of digraphs. We have added a large
number of open problems to the second edition and the book now contains
more than 150 open problems and conjectures, almost twice as many as the
first edition. In order to avoid the book becoming unacceptably long, we had
to remove a significant portion of material from the first edition. We have
tried to do this as carefully as possible so that most of the information in the
first edition is still available, along with a very large number of new results.
Even though this book should not be seen as an encyclopedia on directed
graphs, we included as many important results as possible. The book con-
tains a considerable number of proofs, illustrating various approaches and
techniques used in digraph theory and algorithms.
One of the main features of this book is the strong emphasis on algorithms.
This is something which is regrettably omitted in many books on graphs.
Algorithms on (directed) graphs often play an important role in problems
arising in several areas, including computer science and operations research.
Secondly, many problems on (directed) graphs are inherently algorithmic.
Hence, whenever possible we give constructive proofs of the results in the
book. From these proofs one can very often extract an efficient algorithm
for the problem studied. Even though we describe many algorithms, partly
vii

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin