Graduate students and researchers in combinatorics and matroid theory as well as computer scientists, graph theorists and scientific libraries may find this book useful. Matroids were introduced in 1935 as an abstract generalization of graphs and matrices. Since the mid-1950s, much progress has been made, and there now exists a large collection of significant matroid theorems. Matroid decomposition covers the area of the theory dealing with decomposition and composition of matroids. In order to make the subject more accessible to those without a background in matroid theory, the book starts with introductory material. The exposition is clear and simple, making the main results easily understandable.
- Hardback | 408 pages
- 152.4 x 226.06 x 25.4mm | 725.74g
- 01 Sep 1992
- Elsevier Science Publishing Co Inc
- Academic Press Inc
- San Diego, United States
- references, indexes
Table of contents
Historical notes. Part 1 Basic definition: overview and notation; graph definitions; matrix definitions; complexity of algorithms. Part 2 From graphs to matroids: overview; graphs produce graphic matroids; binary matroids generalize graphic matroids; abstract matrices produce all matroids; characterization of binary matroids. Part 3 Series-parallel and delta-wye constructions: overview; series-parallel construction; delta-wye construction for graphs; delta-wye construction for binary matroids; applications, extensions. Part 4 Path shortening technique: overview; shortening of paths; intersection and partitioning of matroids; extensions. Part 5 Separation algorithm: overview; separation algorithm; sufficient condition for induced separations; extensions of 3-connected minors; extensions. Part 6 Splitter theorem and sequences of nested minors: overview; splitter theorem; sequences of nested minors and wheel theorem; characterization of planar graphs; extensions. Part 7 Matroid sums: overview; 1 - and 2 - sums; general k-sums; finding 1-, 2-, and 3- sums; delta-sum and wye-sum. Part 8 Matrix total unimodularity and matroid regularity: overview; basic results and applications of total unimodularity; characterization of regular matroids; characterization of ternary matroids; extensions and references. Part 9 Graphic matroids: overview; characterization of regular matroids; characterization of ternary matroids; extensions and references. Part 10 Graphic matroids: overview; characterization of planar matroids; regular matroids with M(K3,3) minors; characterization of graphic matroids; decomposition theorems for graphs; testing graphicness of binary matroids; applications, extensions and references. Part 11 Overview; 1-2 2-, and 3- sum compositions preserve regularity; regular matroid decommposition theorem; testing matroids regulariy and matrix total unimodularity; applications of regular matroid decomposition theorem; extensions and references. Part 12 Almost regular matroids: overview; characterization of alpha-balanced graphs; several matrix classes; definition and construction of almost regular matroids; matrix constructions; applications, extensions, and references. Part 13 Max-flow min-cut matroids: overview; 2-sum and delta-sum decompositions; characterization of max-flow min-cut matroids and polynominal algorithms; graphs without odd-K4 minors; applications, extensions.