Greedy and heuristic algorithms for codes and colorings
Authors:
- P.R.J. OstergardPOP.R.J. Ostergard
- 1 January 1998
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 44 (1) , 382-388
Abstract
Many of the fundamental coding problems can be represented as graph problems. These problems are often intrinsically difficult and unsolved even if the code length is relatively small. With the motivation to improve lower bounds on the sizes of constant weight codes and asymmetric codes, we suggest a few greedy algorithms and other heuristic methods, which result in new, record-breaking codes. Some of the heuristics used are based on tabu search and evolutionary algorithms. Tables of new codes are presentedKeywords
This publication has 16 references indexed in Scilit:
- Bounds on mixed binary/ternary codesIEEE Transactions on Information Theory, 1998
- New constant weight codes from linear permutation groupsIEEE Transactions on Information Theory, 1997
- On the chromatic number, colorings, and codes of the Johnson graphDiscrete Applied Mathematics, 1996
- Bounds and constructions of asymmetric or unidirectional error-correcting codesApplicable Algebra in Engineering, Communication and Computing, 1992
- New lower bounds for asymmetric and unidirectional codesIEEE Transactions on Information Theory, 1991
- A new table of constant weight codesIEEE Transactions on Information Theory, 1990
- The priority-based coloring approach to register allocationACM Transactions on Programming Languages and Systems, 1990
- New lower bounds for constant weight codesIEEE Transactions on Information Theory, 1989
- The constantinrao construction for binary asymmetric error-correcting codesInformation and Control, 1980
- An application of graph coloring to printed circuit testingIEEE Transactions on Circuits and Systems, 1976