LINEAR-TIME COMPUTATION OF OPTIMAL SUBGRAPHS OF DECOMPOSABLE GRAPHS

被引：124

作者：

BERN, MW ^{[1
]}

LAWLER, EL ^{[1
]}

WONG, AL ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY,DIV COMP SCI,BERKELEY,CA 94720

来源：

JOURNAL OF ALGORITHMS | 1987年 / 8卷 / 02期

关键词：

D O I：

10.1016/0196-6774(87)90039-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：216 / 235

页数：20

共 23 条

[11]

HOPCROFT JE, 1979, INTRO AUTOMATA THEOR, P65

[12] A LINEAR ALGORITHM FOR THE DOMINATION NUMBER OF A SERIES-PARALLEL GRAPH [J].

KIKUNO, T ;

YOSHIDA, N ;

KAKUDA, Y .

DISCRETE APPLIED MATHEMATICS, 1983, 5 (03) :299-311

[13] ON THE ALGORITHMIC COMPLEXITY OF TOTAL DOMINATION [J].

LASKAR, R ;

PFAFF, J ;

HEDETNIEMI, SM ;

HEDETNIEMI, ST .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (03) :420-425

[14]

MITCHELL S, 1977, 8TH P SE C COMB GRAP, P489

[15]

MONIEN D, 1981, 13TH P ANN S THEOR C, P207

[16] OPTIMUM DOMINATION IN WEIGHTED TREES [J].

NATARAJAN, KS ;

WHITE, LJ .

INFORMATION PROCESSING LETTERS, 1978, 7 (06) :261-265

[17]

Pfaff J., 1984, C NUMER, V45, P71

[18]

PFAFF J, 1983, 428 CLEMS U TECH REP

[19] DYNAMIC-PROGRAMMING ALGORITHMS FOR RECOGNIZING SMALL-BANDWIDTH GRAPHS IN POLYNOMIAL-TIME [J].

SAXE, JB .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1980, 1 (04) :363-369

[20] LINEAR-TIME COMPUTABILITY OF COMBINATORIAL PROBLEMS ON SERIES-PARALLEL GRAPHS [J].

TAKAMIZAWA, K ;

NISHIZEKI, T ;

SAITO, N .

JOURNAL OF THE ACM, 1982, 29 (03) :623-641

← 1 2 3 →