Augmenting the algebraic connectivity for certain families of graphs

被引：1

作者：

Justel, Claudia ^{[1
]}

Rocha, Carlos ^{[1
]}

Chaves, Emanuelle ^{[1
]}

Chaves, Anderson ^{[1
]}

Avelino, Geraldo ^{[1
]}

机构：

[1] Inst Mil Engn, Rio De Janeiro, Brazil

来源：

DISCRETE APPLIED MATHEMATICS | 2019年 / 253卷

关键词：

Graph spectra; Laplacian matrix; Algebraic connectivity; Approximated algorithm;

D O I：

10.1016/j.dam.2018.03.069

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In this work we compare solutions of two distinct algorithms that try to increase the value of the algebraic connectivity of a given graph by choosing, with different strategies, edges to be included. Eccentricity and Perturbation Heuristics were considered, as well as random graphs and special families of trees being inputs of those algorithms. As conclusions of the reported experiments, the Eccentricity Heuristic obtains good results when compared with Perturbation Heuristic and a conjecture about broom trees is presented. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：51 / 60

页数：10

共 18 条

[1]

[Anonymous], 1998, The Electronic Journal of Linear Algebra

[2] Old and new results on algebraic connectivity of graphs [J].

de Abreu, Nair Maria Maia .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 423 (01) :53-73

[3]

de Oliveira C. C. G. F., 2012, P WORLDCOMP, P1

[4]

Diestel R., 2000, GRAPH THEORY, DOI DOI 10.1007/978-3-662-53622-3

[5]

FIEDLER M, 1975, CZECH MATH J, V25, P607

[6]

FIEDLER M, 1973, CZECH MATH J, V23, P298

[7] Growing well-connected graphs [J].

Ghosh, Arpita ;

Boyd, Stephen .

PROCEEDINGS OF THE 45TH IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-14, 2006, :6605-6611

[8] ORDERING TREES BY ALGEBRAIC CONNECTIVITY [J].

GRONE, R ;

MERRIS, R .

GRAPHS AND COMBINATORICS, 1990, 6 (03) :229-237

[9]

Justel C., 2016, ELECT NOTES DISCRETE, V55, P13

[10]

Kirkland S., 2007, HDB LINEAR ALGEBRA

← 1 2 →