Placement Delivery Array Design through Strong Edge Coloring of Bipartite Graphs
arXiv:1609.02985 · doi:10.1109/LCOMM.2017.2765629
Abstract
The technique of coded caching proposed by Madddah-Ali and Niesen is a promising approach to alleviate the load of networks during busy times. Recently, placement delivery array (PDA) was presented to characterize both the placement and delivery phase in a single array for the centralized coded caching algorithm. In this paper, we interpret PDA from a new perspective, i.e., the strong edge coloring of bipartite graph. We prove that, a PDA is equivalent to a strong edge colored bipartite graph. Thus, we can construct a class of PDAs from existing structures in bipartite graphs. The class includes the scheme proposed by Maddah-Ali \textit{et al.} and a more general class of PDAs proposed by Shangguan \textit{et al.} as special cases. Moreover, it is capable of generating a lot of PDAs with flexible tradeoff between the sub-packet level and load.
5 pages, 2 figures
References in corpus (3)
Cited by in corpus (28)
- Subexponential and Linear Subpacketization Coded Caching via Projective Geometry
- Subpacketization in Coded Caching with Demand Privacy
- A Novel Transformation Approach of Shared-link Coded Caching Schemes for Multiaccess Networks
- Some new Constructions of Coded Caching Schemes with Reduced Subpacketization
- Key Superposition Simultaneously Achieves Security and Privacy in Cache-Aided Linear Function Retrieval
- Novel Frameworks for Coded Caching via Cartesian Product with Reduced Subpacketization
- Coded Caching Schemes with Reduced Subpacketization from Linear Block Codes
- On the Placement and Delivery Schemes for Decentralized Coded Caching System
- Placement Delivery Array Design for Combination Networks with Edge Caching
- Linear Coded Caching Scheme for Centralized Networks
- A Multi-Antenna Coded Caching Scheme with Linear Subpacketization
- A Novel Recursive Construction for Coded Caching Schemes
- A framework of constructing placement delivery arrays for centralized coded caching
- From Centralized to Decentralized Coded Caching
- Reduce Transmission Delay for Cache-Aided Two-Layer Network
- A new Capacity-Achieving Private Information Retrieval Scheme with (Almost) Optimal File Length for Coded Servers
- Placement Delivery Arrays from Combinations of Strong Edge Colorings
- Some new bounds of placement delivery arrays
- Symmetric uncoded caching schemes with low subpacketization levels
- Placement Delivery Array Design via Attention-Based Deep Neural Network
- Improved Constructions of Coded Caching Schemes for Combination Networks
- A Low-Subpacketization High-Performance MIMO Coded Caching Scheme
- A Fundamental Storage-Communication Tradeoff for Distributed Computing with Straggling Nodes
- Robust and Secure Cache-aided Private Linear Function Retrieval from Coded Servers
- New coded caching schemes from placement delivery arrays
- Coded Caching Schemes with Linear Subpacketizations
- On the Dynamic Centralized Coded Caching Design
- Vertex Ordering Algorithms for Graph Coloring Problem