A DATA STRUCTURE USEFUL FOR FINDING HAMILTONIAN CYCLES

被引：17

作者：

CHROBAK, M ^{[1
]}

SZYMACHA, T ^{[1
]}

KRAWCZYK, A ^{[1
]}

机构：

[1] UNIV WARSAW,INST MATH,PKIN IX P,PL-00901 WARSAW,POLAND

来源：

THEORETICAL COMPUTER SCIENCE | 1990年 / 71卷 / 03期

关键词：

D O I：

10.1016/0304-3975(90)90053-K

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a data structure, called the reversable AVL-trees, for maintaining a sequence of special operations called reversals. This data structure is based on balanced trees, and it yields an algorithm with complexity O(m log n), where m is the number of reversals. © 1990.

引用

页码：419 / 424

页数：6

共 10 条

[1]

[Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265

[2]

Berge C., 1973, GRAPHS HYPERGRAPHS

[3]

BOLLOBAS B, 1975, 17TH P STOC, P359

[4]

Bollobas B., 1978, LONDON MATH SOC MONO

[5]

Karp Richard M., 1976, ALGORITHMS COMPLEXIT, P1

[6]

Knuth D.E., 1997, ART COMPUTER PROGRAM, V3

[7]

KRAWCZYK A, UNPUB

[8]

POLJAK S, 1982, COMM MATH U CAR, V23, P337

[9] HAMILTONIAN CIRCUITS IN RANDOM GRAPHS [J].

POSA, L .

DISCRETE MATHEMATICS, 1976, 14 (04) :359-364

[10]

THOMASON AG, 1978, ANN DISCRETE MATH, V3, P259

← 1 →