Augmenting the Rigidity of a Graph in R2

被引：0
作者：
A. García
J. Tejel
机构：
[1] Universidad de Zaragoza,Dep. Métodos Estadísticos, IUMA, Facultad de Ciencias
来源：
Algorithmica | 2011年 / 59卷
关键词：
Rigid graph; Laman graph; Augmenting problem; NP-completeness;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Given a Laman graph G, i.e. a minimally rigid graph in R2, we provide a Θ(n2) 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 R2.
引用
收藏
页码：145 / 168
页数：23
相关论文
共 42 条
[1]  
Bang-Jensen J.(1999)Edge-connectivity augmentation with partition constraints SIAM J. Discrete Math. 12 160-207
[2]  
Gabow H.(2003)A proof of Connelly’s conjecture on 3-connected circuits of the rigidity matroid J. Comb. Theory, Ser. B 88 77-97
[3]  
Szigeti Z.(2004)Operations on rigid formations of autonomous agents Commun. Inf. Syst. 3 223-258
[4]  
Jordán T.(1976)Augmentation problems SIAM J. Comput. 5 653-665
[5]  
Berg A.(2006)Source location with rigidity and tree packing requirements Oper. Res. Lett. 34 607-612
[6]  
Jordán T.(2005)Rigid realizations of graphs on small grids Comput. Geom. 32 216-222
[7]  
Eren T.(2000)Incrementing bipartite digraph edge-connectivity J. Comb. Opt. 4 449-486
[8]  
Anderson B.(2005)Planar minimally rigid graphs and pseudo-triangulations Comput. Geom. 31 31-61
[9]  
Morse A.(1992)Conditions for unique graph realizations SIAM J. Comput. 21 65-84
[10]  
Whiteley W.(2005)Connected rigidity matroids and unique realizations of graphs J. Comb. Theory, Ser. B 94 1-29
12345