ON FINDING A CYCLE BASIS WITH A SHORTEST MAXIMAL CYCLE

被引：13

作者：

CHICKERING, DM ^{[1
]}

GEIGER, D ^{[1
]}

HECKERMAN, D ^{[1
]}

机构：

[1] MICROSOFT CORP,REDMOND,WA 98052

来源：

INFORMATION PROCESSING LETTERS | 1995年 / 54卷 / 01期

关键词：

ALGORITHMS; ANALYSIS OF ALGORITHMS; COMBINATORIAL PROBLEMS; CODING THEORY;

D O I：

10.1016/0020-0190(94)00231-M

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Shortest Maximal Cycle Basis (SMCB) problem is that of finding a cycle basis B of a given graph G such that the length of the longest cycle included in B is the smallest among all bases of G. We show that any cycle basis B' of G such that the sum of the lengths of the cycles included in B' is the smallest among all cycle bases of G constitutes a solution to the SMCB problem. Finding a basis with the latter property requires at most O(m(3)n) steps using Horton's algorithm where m is the number of edges and n is the number of vertices.

引用

页码：55 / 58

页数：4

共 12 条

[1]

Berlekamp, McEliece, van Tilborg, On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory, 24, pp. 384-386, (1978)

[2]

Cribb, Ringeisen, Shier, On cycle bases of a graph, Congr. Numer., 32, pp. 221-229, (1981)

[3]

Deo, Minimum length fundamental cycle set, IEEE Trans. Circuits and Systems, 26, pp. 894-895, (1979)

[4]

Deo, Prabhu, Krishnamoorthy, Algorithms for generating fundamental cycles in a graph, ACM Transactions on Mathematical Software, 8, pp. 26-42, (1982)

[5]

Horton, A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM J. Comput., 16, pp. 358-366, (1987)

[6]

Hubicka, Syslo, Minimal bases of cycles of a graph, Proc. Symp. on Recent Advances in Graph Theory, pp. 283-293, (1975)

[7]

Kolasinska, On a minimum cycle basis of a graph, Zastos. Mat., 16, pp. 631-639, (1980)

[8]

Lauritzen, Spiegelhalter, Local comomputations with probabilities on graphical structures and their application to expert system, J. Roy. Statist. Soc. Ser. B, 50, pp. 157-224, (1988)

[9]

Stepanec, Basis systems of vector cycles with extremal properties in graphs, Uspekhi Mat. Nauk, 19, pp. 171-175, (1964)

[10]

Syslo, On cycle bases of a graph, Networks, 9, pp. 123-132, (1979)

← 1 2 →