Finding Cut-Edges and the Minimum Spanning Tree via Semi-Tensor Product Approach

Fan Xujiao (), Xu Yong (), Su Xue () and Wang Jinhuan ()
Additional contact information
Fan Xujiao: School of Science, Hebei University of Technology, Tianjin300401, China
Xu Yong: School of Science, Hebei University of Technology, Tianjin300401, China
Su Xue: School of Science, Hebei University of Technology, Tianjin300401, China
Wang Jinhuan: School of Science, Hebei University of Technology, Tianjin300401, China

Journal of Systems Science and Information, 2018, vol. 6, issue 5, 459-472

Abstract: Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for cycles of graph, based on which a new necessary and sufficient condition is established to find all cycles for any graph. Secondly, using the necessary and sufficient condition of cycles, two algorithms are established to find all cut-edges and the minimum spanning tree, respectively. Finally, the study of an illustrative example shows that the results/algorithms presented in this paper are effective.

Keywords: semi-tensor product; cycle; cut-edge; minimum spanning tree (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.21078/JSSI-2018-459-14 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:jossai:v:6:y:2018:i:5:p:459-472:n:6

DOI: 10.21078/JSSI-2018-459-14

Access Statistics for this article

Journal of Systems Science and Information is currently edited by Shouyang Wang

More articles in Journal of Systems Science and Information from De Gruyter
Bibliographic data for series maintained by Peter Golla ().