Synopses & Reviews
Perceptively written text examines optimization problems that can be formulated in terms of networks and algebraic structures called matroids. Chapters cover shortest paths, network flows, bipartite matching, nonbipartite matching, matroids and the greedy algorithm, matroid intersections, and the matroid parity problems. A suitable text or reference for courses in combinatorial computing and concrete computational complexity in departments of computer science and mathematics.
Table of Contents
Preface Chapter 1 INTRODUCTION Chapter 2 MATHEMATICAL PRELIMINARIES
Chapter 3 SHORTEST PATHS
Chapter 4 NETWORK FLOWS Chapter 5 BIPARTITE MATCHING
Chapter 6 NONBIPARTITE MATCHING Chapter 7 MATROIDS AND THE GREEDY ALGORITHM Chapter 8 MATROID INTERSECTIONS Chapter 9 THE MATROID PARITY PROBLEM
Author Index Subject Index