zbMATH — the first resource for mathematics

Coding over graphs. (English) Zbl 1063.68049
Blaum, Mario (ed.) et al., Information, coding and mathematics. Proceedings of workshop honoring Professor Bob McEliece on his 60th birthday, Pasadena, CA, USA, May 24–25, 2002. Boston, MA: Kluwer Academic Publishers (ISBN 1-4020-7079-9/hbk). The Kluwer International Series in Engineering and Computer Science 687, 355-364 (2002).
Summary: This paper introduces the concept of coding over graphs: given an arbitrary graph, assign information to vertices of the graph in such a way that the information can be retrieved at every vertex by exploring its close proximity. This framework is a generalization of redundant array of inexpensive disks. We study a specific coding over graphs scheme which has the property that as the number of failures increases, the information can be retrieved by exploring slightly larger proximities – therefore a graceful trade-off between reliability and performance is provided. An efficient algorithm for that scheme for the graphs being trees is presented. The algorithm can always find a ‘perfect’ coding over trees scheme.
For the entire collection see [Zbl 1054.94001].
68P20 Information storage and retrieval of data
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
05C90 Applications of graph theory
68R10 Graph theory (including graph drawing) in computer science