Sharifov F. Methods and algorithms for solving problems of design network with complex structure

This thesis focuses on the network design problems under condition that an optimal network must survive with respect to failures of edges of any subgraph which is isomorphic to a given another graph. When the terminals nodes set contains two nodes and the network must be survive with respect to failures of any its edge, the obtained problem is solved by a polynomial time algorithm. We describe a special dual simplex - based methods for finding an optimal solution to the - relaxation of the general location problem. We propose effective algorithms to compute a lower and an upper bounds for the two connected Steiner problem and for the general location problem and for the problems of design networks with several edge disjoint paths between every pair of terminal nodes and for the problems of design networks with given node connectivity requirements. These algorithms were implemented to solve a real large problems. The relaxation of attack problem on a hypergraphs has an integral optimal solution,and when the hypergraph is defined by the vertices set of some single graph, an optimal solution to this problem can be found by polynomial time algorithm. We propose a polynomial time algorithm to solve the multilevel location problem on a tree like networks. We prove that the problem of finding edge and vertex disjoint cycles with a minimum total cost on a directed networks is reduced to the problem of finding two edge disjoint perfect matching on a complete bipartite graph whose edges have two weights. When the difference between two weights of any edge is expressed as a sum of nodes potentials which are end nodes of this edge, the problem is reduced to the Minimum Cost Flow Problem. Keywords: design networks, isomorphic of graphs, hypergraph, submoduar functions, strong polynomial algorithms, polymatroid.