Enumerating spanning and connected subsets in graphs and matroids

被引：7

作者：

Khachiyan, Leonid ^{[2
]}

Boros, Endre ^{[2
]}

Borys, Konrad ^{[2
]}

Elbassioni, Khaled ^{[3
]}

Gurvich, Vladimir ^{[2
]}

Makino, Kazuhisa ^{[1
]}

机构：

[1] Univ Tokyo, Grad Sch Informat Sci & Technol, Tokyo 1138656, Japan

[2] Rutgers State Univ, Piscataway, NJ 08855 USA

[3] Max Planck Inst Informat, Saarbrucken, Germany

来源：

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN | 2007年 / 50卷 / 04期

关键词：

algorithm; matroid; enumeration; quasi-polynomial;

D O I：

10.15807/jorsj.50.325

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal 2-vertex connected subgraphs of a given graph can be generated in incremental polynomial time.

引用

页码：325 / 338

页数：14

共 23 条

[1] Edge-connectivity augmentation with partition constraints [J].

Bang-Jensen, J ;

Gabow, HN ;

Jordán, T ;

Szigeti, Z .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (02) :160-207

[2] COMPLEXITY OF IDENTIFICATION AND DUALIZATION OF POSITIVE BOOLEAN FUNCTIONS [J].

BIOCH, JC ;

IBARAKI, T .

INFORMATION AND COMPUTATION, 1995, 123 (01) :50-63

[3]

Boros E, 2004, LECT NOTES COMPUT SC, V3064, P152

[4] An inequality for polymatroid functions and its applications [J].

Boros, E ;

Elbassioni, K ;

Gurvich, V ;

Khachiyan, L .

DISCRETE APPLIED MATHEMATICS, 2003, 131 (02) :255-281

[5]

Boros E., 2000, SIAM J COMPUT, V30, P2036

[6]

COULBOURN CJ, 1987, COMBINATORICS NETWOR

[7] IDENTIFYING THE MINIMAL TRANSVERSALS OF A HYPERGRAPH AND RELATED PROBLEMS [J].

EITER, T ;

GOTTLOB, G .

SIAM JOURNAL ON COMPUTING, 1995, 24 (06) :1278-1304

[8] New results on monotone dualization and generating hypergraph transversals [J].

Eiter, T ;

Gottlob, G ;

Makino, K .

SIAM JOURNAL ON COMPUTING, 2003, 32 (02) :514-537

[9]

EITER T, 2006, RR18430601 INFSYS TU

[10] On the complexity of dualization of monotone disjunctive normal forms [J].

Fredman, ML ;

Khachiyan, L .

JOURNAL OF ALGORITHMS, 1996, 21 (03) :618-628

← 1 2 3 →