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 [J].

Bang-Jensen, J ;

Gabow, HN ;

Jordán, T ;

Szigeti, Z .

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 [J].

Berg, AR ;

Jordán, T .

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 [J].

Fekete, Z ;

Jordán, T .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2005, 32 (03) :216-222

[10]

Fekete Z, 2004, LECT NOTES COMPUT SC, V3221, P299

← 1 2 3 4 →