On zero-error codes produced by greedy algorithms

被引：0
作者：
Marcin Jurkiewicz
机构：
[1] Gdańsk University of Technology,Faculty of Electronics, Telecommunications and Informatics
来源：
Journal of Combinatorial Optimization | 2022年 / 44卷
关键词：
Shannon capacity; Zero-error code; Greedy algorithm; Strong product; Independence number;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We present two greedy algorithms that determine zero-error codes and lower bounds on the zero-error capacity. These algorithms have many advantages, e.g., they do not store a whole product graph in a computer memory and they use the so-called distributions in all dimensions to get better approximations of the zero-error capacity. We also show an additional application of our algorithms.
引用
收藏
页码：2963 / 2980
页数：17
相关论文
共 38 条
[1]  
Alon N(2006)The Shannon capacity of a graph and the independence numbers of its powers IEEE Trans Inf Theory 52 2172-2176
[2]  
Lubetzky E(2012)Havel–Hakimi residues of unigraphs Inf Process Lett 112 44-48
[3]  
Barrus MD(2015)New potential functions for greedy independence and coloring Discrete Appl Math 182 61-72
[4]  
Borowiecki P(2003)Some remarks on the Shannon capacity of odd cycles Ars Combin 66 243-257
[5]  
Rautenbach D(1991)On the residue of a graph J Graph Theory 15 39-64
[6]  
Codenotti B(2007)Independence number and fullerene stability Chem Phys Lett 448 75-82
[7]  
Gerace I(2012)The chromatic gap and its extremes J Comb Theory Ser B 102 1155-1178
[8]  
Resta G(1973)Numerical invariants and the strong product of graphs J Comb Theory Ser B 15 146-155
[9]  
Favaron O(2001)On the independence number of a graph in terms of order and size Discrete Math 232 131-138
[10]  
Mahéo M(2017)Average distance is submultiplicative and subadditive with respect to the strong product of graphs Appl Math Comput 315 278-285
1234