|
This article is cited in 5 scientific papers (total in 5 papers)
Scientific Part
Computer Sciences
Construction of all minimal edge extensions of the graph with isomorphism rejection
M. B. Abrosimova, H. H. K. Sudaniba, A. A. Lobova a Saratov State University, 83 Astrakhanskaya St., Saratov 410012, Russia
b Ministry of Science and Technology of Iraq, Baghdad, Iraq
Abstract:
In 1993 Frank Harary and John P. Hayes proposed a graph model for investigating edge fault tolerance of discrete systems. The technical system is mapped to a graph. The elements of the system correspond to the vertices of the graph, and links between the elements correspond to edges or arcs of the graph. Failure of a system element refers to the removal of the corresponding vertex from the system graph along with all its edges. The formalization of a fault-tolerant system implementation is the extension of the graph. The graph $G^*$ is called the edge $k$-extension of the graph $G$ if, after removing any $k$ edges from the graph $G^*$ result graph contains the graph $G$. The edge $k$-extension of a graph $G$ is called minimal if it has the least number of vertices and edges among all edge $k$-extensions of a graph $G$. An algorithm for constructing all nonisomorphic minimal edge $k$-extensions of a given graph using methods of canonical representatives and Read–Faradjev are proposed.
Key words:
fault tolerance, edge fault tolerance, graph extension, isomorphism rejection, canonical form, method of generating canonical representatives, Read–Faradjev-type orderly algorithm.
Received: 20.10.2019 Accepted: 02.12.2019
Citation:
M. B. Abrosimov, H. H. K. Sudani, A. A. Lobov, “Construction of all minimal edge extensions of the graph with isomorphism rejection”, Izv. Saratov Univ. Math. Mech. Inform., 20:1 (2020), 105–115
Linking options:
https://www.mathnet.ru/eng/isu832 https://www.mathnet.ru/eng/isu/v20/i1/p105
|
|