The Minimum Spectral Radius of an Edge-Removed Network: A Hypercube Perspective

Joint Authors

Wu, Yingbo
Zhang, Tianrui
Chen, Shan
Wang, Tianhui

Source

Discrete Dynamics in Nature and Society

Issue

Vol. 2017, Issue 2017 (31 Dec. 2017), pp.1-8, 8 p.

Publisher

Hindawi Publishing Corporation

Publication Date

2017-04-19

Country of Publication

Egypt

No. of Pages

8

Main Subjects

Mathematics

Abstract EN

The spectral radius minimization problem (SRMP), which aims to minimize the spectral radius of a network by deleting a given number of edges, turns out to be crucial to containing the prevalence of an undesirable object on the network.

As the SRMP is NP-hard, it is very unlikely that there is a polynomial-time algorithm for it.

As a result, it is proper to focus on the development of effective and efficient heuristic algorithms for the SRMP.

For that purpose, it is appropriate to gain insight into the pattern of an optimal solution to the SRMP by means of checking some regular networks.

Hypercubes are a celebrated class of regular networks.

This paper empirically studies the SRMP for hypercubes with two/three/four missing edges.

First, for each of the three subproblems of the SRMP, a candidate for the optimal solution is presented.

Second, it is shown that the candidate is optimal for small-sized hypercubes, and it is shown that the proposed candidate is likely to be optimal for medium-sized hypercubes.

The edges in each candidate are evenly distributed over the network, which may be a common feature of all symmetric networks and hence is instructive in designing effective heuristic algorithms for the SRMP.

American Psychological Association (APA)

Wu, Yingbo& Zhang, Tianrui& Chen, Shan& Wang, Tianhui. 2017. The Minimum Spectral Radius of an Edge-Removed Network: A Hypercube Perspective. Discrete Dynamics in Nature and Society،Vol. 2017, no. 2017, pp.1-8.
https://search.emarefa.net/detail/BIM-1151118

Modern Language Association (MLA)

Wu, Yingbo…[et al.]. The Minimum Spectral Radius of an Edge-Removed Network: A Hypercube Perspective. Discrete Dynamics in Nature and Society No. 2017 (2017), pp.1-8.
https://search.emarefa.net/detail/BIM-1151118

American Medical Association (AMA)

Wu, Yingbo& Zhang, Tianrui& Chen, Shan& Wang, Tianhui. The Minimum Spectral Radius of an Edge-Removed Network: A Hypercube Perspective. Discrete Dynamics in Nature and Society. 2017. Vol. 2017, no. 2017, pp.1-8.
https://search.emarefa.net/detail/BIM-1151118

Data Type

Journal Articles

Language

English

Notes

Includes bibliographical references

Record ID

BIM-1151118