Augmenting the Rigidity of a Graph in R 2

被引：6

作者：

Garcia, A. ^{[1
]}

Tejel, J. ^{[1
]}

机构：

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

来源：

ALGORITHMICA | 2011年 / 59卷 / 02期

关键词：

Rigid graph; Laman graph; Augmenting problem; NP-completeness; EDGE-CONNECTIVITY AUGMENTATION; PLANE SKELETAL STRUCTURES; PSEUDO-TRIANGULATIONS; REALIZATIONS; ALGORITHMS; NETWORKS;

D O I：

10.1007/s00453-009-9300-9

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Given a Laman graph G, i.e. a minimally rigid graph in R (2), we provide a I similar to(n (2)) algorithm to augment G to a redundantly rigid graph, by adding a minimum number of edges. Moreover, we prove that this problem of augmenting is NP-hard for an arbitrary rigid graph G in R (2).

引用

页码：145 / 168

页数：24

共 34 条

[1] [Anonymous], 1989, Matroid Theory and its Applications in Electric Network Theory and in Statics
[2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[3] [Anonymous], 1999, Rigidity theory and applications
[4] Edge-connectivity augmentation with partition constraints
Bang-Jensen, J
Gabow, HN
Jordán, T
Szigeti, Z
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (02) : 160 - 207
[5] Berg AR, 2003, LECT NOTES COMPUT SC, V2832, P78
[6] A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid
Berg, AR
Jordán, T
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 88 (01) : 77 - 97
[7] Eren T., 2004, Commun. Inf. Syst, V3, P223, DOI DOI 10.4310/CIS.2003.V3.N4.A2
[8] Eswaran K. P., 1976, SIAM Journal on Computing, V5, P653, DOI 10.1137/0205044
[9] Rigid realizations of graphs on small grids
Fekete, Z
Jordán, T
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2005, 32 (03): : 216 - 222
[10] Fekete Z, 2004, LECT NOTES COMPUT SC, V3221, P299

← 1 2 3 4 →