COMBINATORIAL ALGORITHMS ON A CLASS OF GRAPHS

被引：25

作者：

KORNEYENKO, NM ^{[1
]}

机构：

[1] BYELORUSSIAN ACAD SCI, INST MATH, MINSK 220072, BELARUS

来源：

DISCRETE APPLIED MATHEMATICS | 1994年 / 54卷 / 2-3期

关键词：

D O I：

10.1016/0166-218X(94)90022-1

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

[From the original] For a class of graphs containing series-parallel and outerplanar graphs the linear-time solvability of a number of combinatorial problems such as minimum vertex cover, Hamiltonian completion problem, etc., is shown.

引用

页码：215 / 217

页数：3

共 6 条

[1] TOPOLOGY OF SERIES-PARALLEL NETWORKS [J].

DUFFIN, RJ .

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1965, 10 (02) :303-&

[2] ADVANCES ON HAMILTONIAN COMPLETION PROBLEM [J].

GOODMAN, SE ;

HEDETNIEMI, ST .

JOURNAL OF THE ACM, 1975, 22 (03) :352-360

[3]

Harary F., 1994, GRAPH THEORY, P11, DOI [DOI 10.21236/AD0705364, 10.1201/9780429493768, DOI 10.1201/9780429493768]

[4] 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

[5]

TAKAMIZAWA K, 1981, LECTURE NOTES COMPUT, V108, P79

[6] THE RECOGNITION OF SERIES-PARALLEL DIGRAPHS [J].

VALDES, J ;

TARJAN, RE ;

LAWLER, EL .

SIAM JOURNAL ON COMPUTING, 1982, 11 (02) :298-313

← 1 →