Augmenting the Connectivity of Outerplanar Graphs

被引：5

作者：

Garcia, A. ^{[1
]}

Hurtado, F. ^{[2
]}

Noy, M. ^{[2
]}

Tejel, J. ^{[1
]}

机构：

[1] Univ Zaragoza, IUMA, Dep Metodos Estadist, E-50009 Zaragoza, Spain

[2] Univ Politecn Cataluna, Dept Matemat Aplicada 2, ES-08034 Barcelona, Spain

来源：

ALGORITHMICA | 2010年 / 56卷 / 02期

关键词：

Graph augmentation; Outerplanar graph; AUGMENTATION PROBLEMS;

D O I：

10.1007/s00453-008-9167-1

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We provide an optimal algorithm for the problem of augmenting an outerplanar graph G by adding a minimum number of edges in such a way that the augmented graph G' is outerplanar and 2-connected. We also solve optimally the same problem when instead we require G' to be 2-edge-connected.

引用

页码：160 / 179

页数：20

共 12 条

[1] Aho A. V., 1974, The design and analysis of computer algorithms
[2] [Anonymous], 2013, Modern graph theory
[3] Successive edge-connectivity augmentation problems
Cheng, E
Jordán, T
[J]. MATHEMATICAL PROGRAMMING, 1999, 84 (03) : 577 - 593
[4] Eswaran K. P., 1976, SIAM Journal on Computing, V5, P653, DOI 10.1137/0205044
[5] Packing trees into planar graphs
García, A
Hernando, C
Hurtado, F
Noy, M
Tejel, J
[J]. JOURNAL OF GRAPH THEORY, 2002, 40 (03) : 172 - 181
[6] Hsu T., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P70, DOI 10.1109/SFCS.1992.267817
[7] Independence free graphs and vertex connectivity augmentation
Jackson, B
Jordán, T
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2005, 94 (01) : 31 - 77
[8] Augmenting outerplanar graphs
Kant, G
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1996, 21 (01): : 1 - 25
[9] KANT G, 1993, THESIS UTRECHT U
[10] Deterministic (O)over-tilde(nm) time edge-splitting in undirected graphs
Nagamochi, H
Ibaraki, T
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 1997, 1 (01) : 5 - 46

← 1 2 →