On zero-error codes produced by greedy algorithms

DOI10.1007/s10878-021-00825-yzbMath1504.90174OpenAlexW3210710155MaRDI QIDQ2084654

Marcin Jurkiewicz

Publication date: 18 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00825-y

zbMATH Keywords

greedy algorithmindependence numberShannon capacitystrong productzero-error code

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Uses Software

• KronFit

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the independence number of some strong products of cycle-powers
• Exact exponential algorithms.
• Some eigenvalue properties in graphs (conjectures of Graffiti -- II)
• The chromatic gap and its extremes
• Havel-Hakimi residues of unigraphs
• New lower bound on the Shannon capacity of \(C_7\) from circular graphs
• Average distance is submultiplicative and subadditive with respect to the strong product of graphs
• New potential functions for greedy independence and coloring
• New lower bounds for the Shannon capacity of odd cycles
• Numerical invariants and the strong product of graphs
• An approximation of the zero error capacity by a greedy algorithm
• Basic Modern Algebra with Applications
• Handbook of Graph Theory
• The Shannon capacity of a graph and the independence numbers of its powers
• On the residue of a graph
• On the Shannon capacity of a graph
• Zero-error information theory
• The Theory of Information and Coding
• Graph Colorings
• On the Growth of Large Independent Sets in Scale-Free Networks
• Elements of Information Theory
• On a Problem of C. E. Shannon in Graph Theory
• Information Theory
• On the independence number of a graph in terms of order and size