Greedy and heuristic algorithms for codes and colorings

被引：33

作者：

Etzion, T ^{[1
]}

Ostergard, PRJ

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

[2] Helsinki Univ Technol, Dept Comp Sci & Engn, HUT 02015, Finland

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 1998年 / 44卷 / 01期

基金：

美国国家科学基金会;

关键词：

asymmetric code; coloring; constant weight code; evolutionary algorithm; tabu search;

D O I：

10.1109/18.651069

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 presented.

引用

页码：382 / 388

页数：7

共 19 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Back T, 1996, EVOLUTIONARY ALGORIT

[3]

Bitan S., 1993, Designs, Codes and Cryptography, V3, P283, DOI 10.1007/BF01418528

[4] A NEW TABLE OF CONSTANT WEIGHT CODES [J].

BROUWER, AE ;

SHEARER, JB ;

SLOANE, NJA ;

SMITH, WD .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1990, 36 (06) :1334-1380

[5] THE PRIORITY-BASED COLORING APPROACH TO REGISTER ALLOCATION [J].

CHOW, FC ;

HENNESSY, JL .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1990, 12 (04) :501-536

[6]

ETZION T, 1992, IEEE T INFORM THEORY, V38, P1183

[7] NEW LOWER BOUNDS FOR ASYMMETRIC AND UNIDIRECTIONAL CODES [J].

ETZION, T .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1991, 37 (06) :1696-1705

[8] On the chromatic number, colorings, and codes of the Johnson graph [J].

Etzion, T ;

Bitan, S .

DISCRETE APPLIED MATHEMATICS, 1996, 70 (02) :163-175

[9]

ETZION T, 1997, 909 CS TECHN COMP SC

[10]

Fang G., 1992, Applicable Algebra in Engineering, Communication and Computing, V3, P269, DOI 10.1007/BF01294837

← 1 2 →