On rigidity and realizability of weighted graphs

被引:12
作者
Alfakih, AY [1 ]
机构
[1] Tech Univ Munich, Zentrum Math, D-80290 Munich, Germany
关键词
weighted graphs; rigidity; realizations of graphs; Euclidean distance matrices; slater condition; convex sets; semidefinite programming;
D O I
10.1016/S0024-3795(00)00281-0
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Recently, a new characterization of rigid graphs was introduced using Euclidean distance matrices (EDMs) [A.Y. Alfakih, Linear Algebra Appl. 310 (2000) 149]. In this paper, we address the computational aspects of this characterization. Also we present a characterization of graphs which are realizable in R-r For some 1 less than or equal to r less than or equal to n - 2 but not realizable in R(n-1), where n is the number of nodes, (C) 2001 Elsevier Science Inc. All rights reserved. AMS classification: 94C15; 52A20; 05C50: 15A57.
引用
收藏
页码:57 / 70
页数:14
相关论文
共 11 条
[1]   Graph rigidity via Euclidean distance matrices [J].
Alfakih, AY .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2000, 310 (1-3) :149-165
[2]  
[Anonymous], LINEAR INEQUALITIES
[3]  
BERMAN A, 1971, MATH PROGRAM, V1, P291
[4]  
Connelly R., 1993, Handbook of Convex Geometry, P223
[5]  
CRAVEN BD, 1978, MATH PROGRAMMING CON
[6]  
Crippen G. M., 1988, DISTANCE GEOMETRY MO
[7]  
Fan K., 1966, LINEAR INEQUALITIES, P99
[8]   Cuts, matrix completions and graph rigidity [J].
Laurent, M .
MATHEMATICAL PROGRAMMING, 1997, 79 (1-3) :255-283
[9]   RIGID AND FLEXIBLE FRAMEWORKS [J].
ROTH, B .
AMERICAN MATHEMATICAL MONTHLY, 1981, 88 (01) :6-21
[10]  
Schrijver Alexander, 1999, THEORY LINEAR INTEGE