Generating all series-parallel graphs

被引：1

作者：

Kawano, S ^{[1
]}

Nakano, S ^{[1
]}

机构：

[1] Gunma Univ, Dept Comp Sci, Kiryu, Gumma 3768515, Japan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2005年 / E88A卷 / 05期

关键词：

algorithm; enumeration; series-parallel graph;

D O I：

10.1093/ietfec/e88-a.5.1129

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper we give an algorithm to generates all series-parallel graphs with at most m edges. This algorithm generate each series-parallel graph in constant time on average.

引用

页码：1129 / 1135

页数：7

共 12 条

[1]

AHO AV, 1995, FDN COMPUTER SCI

[2]

Algorithms E., 1992, ANN DISCRETE MATH, V53, P221, DOI DOI 10.1016/S0167-5060(08)70325-X

[3]

[Anonymous], 1993, EFFICIENT ALGORITHMS

[4]

[Anonymous], 1989, COMBINATORIAL ALGORI

[5] CONSTANT TIME GENERATION OF ROOTED TREES [J].

BEYER, T ;

HEDETNIEMI, SM .

SIAM JOURNAL ON COMPUTING, 1980, 9 (04) :706-712

[6]

Kreher D. L., 1998, Combinatorial Algorithms: Generation, Enumeration, and Search

[7]

Li G, 1999, 10 ANN ACM SIAM S DI, P939

[8]

Li ZJ, 2001, LECT NOTES COMPUT SC, V2076, P433

[9] Isomorph-free exhaustive generation [J].

McKay, BD .

JOURNAL OF ALGORITHMS, 1998, 26 (02) :306-324

[10] Efficient generation of triconnected plane triangulations [J].

Nakano, S .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 27 (02) :109-122

← 1 2 →