L(2,1,1)-Labeling Is NP-Complete for Trees

被引：0

作者：

Golovach, Petr A. ^{[1
]}

Lidicky, Bernard ^{[2
,3
]}

Paulusma, Daniel ^{[1
]}

机构：

[1] Univ Durham, Dept Comp Sci, Sci Labs, South Rd, Durham DH1 3LE, England

[2] Charles Univ Prague, Fac Math & Phys, DIMATIA, CR-11800 Prague, Czech Republic

[3] Inst Theoret Comp Sci ITI, CR-11800 Prague, Czech Republic

来源：

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS | 2010年 / 6108卷

基金：

英国工程与自然科学研究理事会;

关键词：

DISTANCE CONSTRAINED LABELINGS; GRAPHS; TREEWIDTH;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An L(p(1), p(2), p(3))-labeling of a graph G with span lambda is a mapping f that assigns each vertex u of G an integer label 0 <= f(u) <= lambda such that vertical bar f(u) - f(v)vertical bar >= p(i) whenever vertices u and v are of distance i for i is an element of {1, 2, 3}. We show that testing whether a given graph has an L(2, 1, 1)-labeling with some given span lambda is NP-complete even for the class of trees.

引用

页码：211 / +

页数：2

共 18 条

[1]

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

[2]

BERTOSSI AA, 2003, 17 INT S PAR DISTR P, P222

[3] The L(h, k)-labelling problem:: A survey and annotated bibliography [J].

Calamoneri, Tiziana .

COMPUTER JOURNAL, 2006, 49 (05) :585-608

[4] On L(d, 1)-labelings of graphs [J].

Chang, GJ ;

Ke, WT ;

Kuo, D ;

Liu, DDF ;

Yeh, RK .

DISCRETE MATHEMATICS, 2000, 220 (1-3) :57-66

[5] The L(2,1)-labeling problem on graphs [J].

Chang, GJ ;

Kuo, D .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (02) :309-316

[6] THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .1. RECOGNIZABLE SETS OF FINITE GRAPHS [J].

COURCELLE, B .

INFORMATION AND COMPUTATION, 1990, 85 (01) :12-75

[7]

Fiala J, 2005, LECT NOTES COMPUT SC, V3580, P360

[8]

Fiala J, 2004, LECT NOTES COMPUT SC, V3353, P58

[9] Fixed-parameter complexity of λ-labelings [J].

Fiala, J ;

Kloks, T ;

Kratochvíl, J .

DISCRETE APPLIED MATHEMATICS, 2001, 113 (01) :59-72

[10]

FIALA J., 2002, Discuss. Math. Graph Theory, V22, P89

← 1 2 →