COMPUTING THE BINDING NUMBER OF A GRAPH

被引：15

作者：

CUNNINGHAM, WH

机构：

[1] Department of Mathematics and Statistics, Carleton University, Ottawa

来源：

DISCRETE APPLIED MATHEMATICS | 1990年 / 27卷 / 03期

关键词：

D O I：

10.1016/0166-218X(90)90072-K

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The binding number of a graph G = (V,E) is min(|N(A)|{plus 45 degree rule}|A|: Ø≠A⊆V,N(A)≠V), where N(A) is the set of neighbours of A. This invariant is shown to be computable in polynomial time. © 1990.

引用

页码：283 / 285

页数：3

共 9 条

[1]

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

[2]

[Anonymous], 1971, J COMBIN THEORY

[3]

BAUER D, 1988, RECOGNIZING TOUGH GR

[4]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[5] OPTIMAL ATTACK AND REINFORCEMENT OF A NETWORK [J].

CUNNINGHAM, WH .

JOURNAL OF THE ACM, 1985, 32 (03) :549-561

[6] A FAST PARAMETRIC MAXIMUM FLOW ALGORITHM AND APPLICATIONS [J].

GALLO, G ;

GRIGORIADIS, MD ;

TARJAN, RE .

SIAM JOURNAL ON COMPUTING, 1989, 18 (01) :30-55

[7]

Gondran M, 1984, GRAPHS ALGORITHMS

[8]

GUSFIELD D, 1987, COMPUTING STRENGTH N

[9]

Woodall D. R., 1973, Journal of Combinatorial Theory, Series B, V15, P225, DOI 10.1016/0095-8956(73)90038-5

← 1 →