On rigidity and realizability of weighted graphs

被引：12

作者：

Alfakih, AY ^{[1
]}

机构：

[1] Tech Univ Munich, Zentrum Math, D-80290 Munich, Germany

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2001年 / 325卷 / 1-3期

关键词：

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

← 1 2 →