Graph Algorithms (2nd Edition) - Shimon Even, Guy Even [2011, ISBN 0521517184].pdf

(1161 KB) Pobierz
Graph Algorithms, 2nd Edition
Shimon Even’s
Graph Algorithms,
published in 1979, was a seminal introductory book
on algorithms read by everyone engaged in the field. This thoroughly revised second
edition, with a foreword by Richard M. Karp and notes by Andrew V. Goldberg, continues
the exceptional presentation from the first edition and explains algorithms in formal but
simple language with a direct and intuitive presentation.
The material covered by the book begins with basic material, including graphs and
shortest paths, trees, depth-first search, and breadth-first search. The main part of the
book is devoted to network flows and applications of network flows. The book ends with
two chapters on planar graphs and on testing graph planarity.
(1935–2004) was a pioneering researcher on graph algorithms and
cryptography. He was a highly influential educator who played a major role in establish-
ing computer science education in Israel at the Weizmann Institute and the Technion.
He served as a source of professional inspiration and as a role model for generations
of students and researchers. He is the author of
Algorithmic Combinatorics
(1973) and
Graph Algorithms
(1979).
SHIMON EVEN
Graph Algorithms
2nd Edition
SHIMON EVEN
Edited by
GUY EVEN
Tel-Aviv University
CAMBRIDGE UNIVERSITY PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town,
Singapore, São Paulo, Delhi, Tokyo, Mexico City
Cambridge University Press
32 Avenue of the Americas, New York, NY 10013-2473, USA
www.cambridge.org
Information on this title:
www.cambridge.org/9780521736534
© Shimon Even 1979
© Shimon Even and Guy Even 2012
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without the written
permission of Cambridge University Press.
First edition published 1979 by Computer Science Press
Second edition published 2012
Printed in the United States of America
A catalog record for this publication is available from the British Library.
Library of Congress Cataloging in Publication Data
ISBN 978-0-521-51718-8 Hardback
ISBN 978-0-521-73653-4 Paperback
Cambridge University Press has no responsibility for the persistence or accuracy of URLs
for external or third-party Internet Web sites referred to in this publication and does not
guarantee that any content on such Web sites is, or will remain, accurate or appropriate.
Contents
Foreword by Richard M. Karp
Preface to the Second Edition
Preface to the First Edition
1
Paths in Graphs
1.1 Introduction to Graph Theory
1.2 Computer Representation of Graphs
1.3 Euler Graphs
1.4 De Bruijn Sequences
1.5 Shortest-Path Algorithms
1.6 Problems
Trees
2.1 Tree Definitions
2.2 Minimum Spanning Tree
2.3 Cayley’s Theorem
2.4 Directed Tree Definitions
2.5 The Infinity Lemma
2.6 Problems
Depth-First Search
3.1 DFS of Undirected Graphs
3.2 Algorithm for Nonseparable Components
3.3 DFS on Directed Graphs
3.4 Strongly Connected Components of a Digraph
3.5 Problems
Ordered Trees
4.1 Uniquely Decipherable Codes
v
page
vii
ix
xi
1
1
3
6
9
11
22
29
29
31
34
37
39
42
46
46
52
57
58
62
65
65
2
3
4

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin