Preface; Contents; List of Figures; List of Tables; 1 Introduction; 1.1 Preliminaries and Notation; 1.2 List of Symbols and Operators; References; 2 Submodular Information Flow Models for Multicast Communication; 2.1 Cut Model; 2.2 Graph Model; 2.3 Hypergraph Model; 2.4 Polymatroid Broadcast Model; 2.5 Transformation of Models; 2.6 Generalized Cut Model; 2.7 Penalized Polymatroid Broadcast Model; 2.8 Rate Region Properties and Equivalence; 2.9 Cut Rate Sandwiched Multicast Source Rate Regions; 2.10 Extension to Per-terminal Cut Models; 2.11 Proofs; 2.11.1 Polymatroid Max-Flow Min-Cut Theorem

2.11.2 Transformation of Models2.11.3 Rate Region Properties and Equivalence; 2.11.4 Cut Rate Sandwiched Multicast Source Rate Regions; References; 3 Network Utility Maximization via Submodular Dual Decomposition; 3.1 Concave Network Utility Maximization; 3.2 Dual Decomposition Approach for Min-Cut Rate Regions; 3.3 Dual Decomposition Approach for Max-Flow Regions; 3.4 Connections Between the Dual Decomposition Approaches; 3.5 Dual Decomposition Approach for Hyperarc Rate Regions; 3.6 Convexity and Comprehensiveness; 3.7 Upper Bound for Nonsubmodular Cut Rate Regions

3.8 Counting Set Function Evaluations3.9 Discussion and Related Dual Decomposition Methods; 3.10 Extension to Per-terminal Cut Models; 3.11 Proofs and Appendices; 3.11.1 Utility Characterization of the Multicast Rate Region; 3.11.2 Network Utility Maximization Problem; 3.11.3 Dual Decomposition Approaches; 3.11.4 Convexity and Comprehensiveness; References; 4 Network Coding Bounds and Submodularity; 4.1 Discrete Memoryless Multicast Networks; 4.1.1 Cut-Set Outer Bound; 4.1.2 Noisy Network Coding Inner Bound; 4.1.3 Elementary Hypergraph Decomposition Inner Bound

4.1.4 Weighted Sum Multicast Rate Maximization4.2 Networks of Independent Broadcast Channels; 4.2.1 Cut-Set Outer Bound; 4.2.2 Noisy Network Coding Inner Bound; 4.2.3 Elementary Broadcast Decomposition Inner Bound; 4.2.4 Elementary Broadcast Decomposition for Less Noisy Channels; 4.2.5 Weighted Sum Multicast Rate Maximization; 4.3 Discrete Memoryless Networks with Known State Sequence; 4.3.1 Cut-Set Outer Bound; 4.3.2 Noisy Network Coding Inner Bound; 4.4 Proofs; 4.4.1 Cut-Set Outer Bound; 4.4.2 Noisy Network Coding Inner Bound; 4.4.3 Networks of Independent Broadcast Channels; References

5 Deterministic and Linear Finite Field Networks5.1 Deterministic Networks; 5.1.1 Bounds on the Multicast Capacity Region; 5.1.2 Weighted Sum Source Rate Maximization; 5.2 Networks of Independent Deterministic Broadcast Channels; 5.2.1 Broadcast Representation of the Capacity Region; 5.2.2 Insufficiency of the Hyperarc Model; 5.2.3 Weighted Sum Source Rate Maximization; 5.3 Noisy Linear Finite Field Networks; 5.3.1 Cut-Set Outer Bound; 5.3.2 Noisy Network Coding Inner Bound; 5.3.3 Tightness of Inner and Outer Bounds; 5.3.4 Deterministic Linear Finite Field Networks