Tree powers

被引：43

作者：

Kearney, PE ^{[1
]}

Corneil, DG

机构：

[1] Univ Toronto, Dept Comp Sci, Toronto, ON M5S 3G4, Canada

[2] Univ Waterloo, Dept Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

JOURNAL OF ALGORITHMS | 1998年 / 29卷 / 01期

基金：

加拿大自然科学与工程研究理事会;

关键词：

D O I：

10.1006/jagm.1998.9999

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present the first polynomial algorithm for recognizing tree powers. A graph G is a tr ee power if there is a tree T and a positive integer k such that T-k congruent to G, where x and y are adjacent in T-k if and only if d(T) (x, y) less than or equal to k. We also show that a natural extension of tree power recognition is NP-complete, namely, given a graph G and a positive integer r, determine if there is a tree power within r edges of G. (C) 1998 Academic Press.

引用

页码：111 / 131

页数：21

共 21 条

[1]

[Anonymous], 1987, CONGRES NUMER

[2]

[Anonymous], 1968, J COMBIN THEORY

[3] CHARACTERIZATIONS OF TOTALLY BALANCED MATRICES [J].

ANSTEE, RP ;

FARBER, M .

JOURNAL OF ALGORITHMS, 1984, 5 (02) :215-230

[4] POWERS OF CHORDAL GRAPHS [J].

BALAKRISHNAN, R ;

PAULRAJA, P .

JOURNAL OF THE AUSTRALIAN MATHEMATICAL SOCIETY SERIES A-PURE MATHEMATICS AND STATISTICS, 1983, 35 (OCT) :211-217

[5] DISTANCES IN COCOMPARABILITY GRAPHS AND THEIR POWERS [J].

DAMASCHKE, P .

DISCRETE APPLIED MATHEMATICS, 1992, 35 (01) :67-72

[6]

Escalante F., 1974, Journal of Combinatorial Theory, Series B, V16, P282, DOI 10.1016/0095-8956(74)90074-4

[7] CHARACTERIZATIONS OF STRONGLY CHORDAL GRAPHS [J].

FARBER, M .

DISCRETE MATHEMATICS, 1983, 43 (2-3) :173-189

[8]

Garey M. S., 1979, COMPUTERS INTRACTIBI

[9] COMPLEXITY AND ALGORITHMS FOR REASONING ABOUT TIME - A GRAPH-THEORETIC APPROACH [J].

GOLUMBIC, MC ;

SHAMIR, R .

JOURNAL OF THE ACM, 1993, 40 (05) :1108-1133

[10]

GOLUMBIC MC, 1993, IN PRESS ADV APPL MA

← 1 2 3 →