Recently, the inverse connected p-median problem on block graphs G(V,E,w) under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. Their contributions include finding a nece...Recently, the inverse connected p-median problem on block graphs G(V,E,w) under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. Their contributions include finding a necessary and sufficient condition for the connected p-median problem on block graphs, developing algorithms and showing that these problems can be solved in O(n log n) time, where n is the number of vertices in the underlying block graph. Using similar technique, we show that some results are incorrect by a counter-example. Then we redefine some notations, reprove Theorem 1 and redescribe Theorem 2, Theorem 3 and Theorem 4.展开更多
The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes f...The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.展开更多
A connected graph, whose blocks are all cliques （of possibly varying sizes）, is called a block graph. Let D（G） be its distance matrix. In this note, we prove that the Smith normal form of D（G） is independent of ...A connected graph, whose blocks are all cliques （of possibly varying sizes）, is called a block graph. Let D（G） be its distance matrix. In this note, we prove that the Smith normal form of D（G） is independent of the interconnection way of blocks and give an explicit expression for the Smith normal form in the case that all cliques have the same size, which generalize the results on determinants.展开更多
Blockage is a kind of phenomenon occurring frequently in modern transportation network. This paper deals with the research work on the blocking now in a network with the help of network flow theory. The blockage pheno...Blockage is a kind of phenomenon occurring frequently in modern transportation network. This paper deals with the research work on the blocking now in a network with the help of network flow theory. The blockage phenomena can be divided intO local blockage and network blockage. In this paper, which deals mainly with the latter, the fundamental concepts and definitions of network blocking flow, blocking outset are presented and the related theorems are proved. It is proved that the sufficient and necessary condition for the emergence of a blocking now in a network is the existence of the blocking outset. The necessary conditions for the existence of the blocking outset in a network are analysed and the characteristic cutset of blockage which reflects the all possible situation of blocking nows in the network is defined.In the last part of the paper the mathematical model of the minimum blocking now is developed and the solution to a small network is given.展开更多
Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch bonds of G are got.
This paper deals with the research work on the phenomena of local blockage in a transportation network. Onthe basis of introducing the research results in [1], theminimum now capacity problem of a network in the mosts...This paper deals with the research work on the phenomena of local blockage in a transportation network. Onthe basis of introducing the research results in [1], theminimum now capacity problem of a network in the mostseriously blocked situation is studied. With the conceptof complete outset presented in [1], the relationship between the minimum now capacity of a network and its minimum complete cut capacity is discussed, and the reasons for the difference betweent the minimum now capacity of a network and its minimum complete cut capa-city are analysed. In order to get the solution to the problem, the concepts of normalization of a network and its blocking path graph are presented. In the paper it is proved that the necessary and sufficient conditions for the equality between the minumum now capacity and its minumum complete cut capacity are the existence of a feasible flow in the blocking path graph. For the reason that there are some dependent production points in the blocking path graph of a network, the proof about the tenability of the Gale's Theorm for the planat normalized network without circuit is made.展开更多
文摘Recently, the inverse connected p-median problem on block graphs G(V,E,w) under various cost functions, say rectilinear norm, Chebyshev norm, and bottleneck Hamming distance. Their contributions include finding a necessary and sufficient condition for the connected p-median problem on block graphs, developing algorithms and showing that these problems can be solved in O(n log n) time, where n is the number of vertices in the underlying block graph. Using similar technique, we show that some results are incorrect by a counter-example. Then we redefine some notations, reprove Theorem 1 and redescribe Theorem 2, Theorem 3 and Theorem 4.
基金Supported by the National Natural Science Foundation of China(No.11301475,11126202,11171207)the Nature Science Foundation of Zhejiang Province(No.LQ12A01011)partially supported by The Hong Kong CERG Research Fund PolyU 5515/10H
文摘The backup 2-median problem is a location problem to locate two facilities at vertices with the minimum expected cost where each facility may fail with a given probability. Once a facility fails, the other one takes full responsibility for the services. Here we assume that the facilities do not fail simultaneously. In this paper, we consider the backup 2-median problem on block graphs where any two edges in one block have the same length and the lengths of edges on different blocks may be different. By constructing a tree-shaped skeleton of a block graph, we devise an O（n log n q- m）-time algorithm to solve this problem where n and m are the number of vertices and edges, respectively, in the given block graph.
基金supported by the National Natural Science Foundation of China(Nos.11501188,11326057,11171102)by Aid program for Science and Technology Innovative Research Team in Higher Educational Institutions of Hunan Province
文摘A connected graph, whose blocks are all cliques （of possibly varying sizes）, is called a block graph. Let D（G） be its distance matrix. In this note, we prove that the Smith normal form of D（G） is independent of the interconnection way of blocks and give an explicit expression for the Smith normal form in the case that all cliques have the same size, which generalize the results on determinants.
文摘Blockage is a kind of phenomenon occurring frequently in modern transportation network. This paper deals with the research work on the blocking now in a network with the help of network flow theory. The blockage phenomena can be divided intO local blockage and network blockage. In this paper, which deals mainly with the latter, the fundamental concepts and definitions of network blocking flow, blocking outset are presented and the related theorems are proved. It is proved that the sufficient and necessary condition for the emergence of a blocking now in a network is the existence of the blocking outset. The necessary conditions for the existence of the blocking outset in a network are analysed and the characteristic cutset of blockage which reflects the all possible situation of blocking nows in the network is defined.In the last part of the paper the mathematical model of the minimum blocking now is developed and the solution to a small network is given.
基金Supported by the National Natural Science Foundation of China(2 0 0 0 CG0 1 0 3) the Fund of"The Developing Program for Outstanding Person"in NPUS & T Innovation Foundation for Young Teachers of Northwestern Polytechnical University.
文摘In this paper, the spectrum and characteristic polynomial for a special kind of symmetric block circulant matrices are given.
文摘Two methods for determining the supereulerian index of a graph G are given. A sharp upper bound and a sharp lower bound on the supereulerian index by studying the branch bonds of G are got.
文摘This paper deals with the research work on the phenomena of local blockage in a transportation network. Onthe basis of introducing the research results in [1], theminimum now capacity problem of a network in the mostseriously blocked situation is studied. With the conceptof complete outset presented in [1], the relationship between the minimum now capacity of a network and its minimum complete cut capacity is discussed, and the reasons for the difference betweent the minimum now capacity of a network and its minimum complete cut capa-city are analysed. In order to get the solution to the problem, the concepts of normalization of a network and its blocking path graph are presented. In the paper it is proved that the necessary and sufficient conditions for the equality between the minumum now capacity and its minumum complete cut capacity are the existence of a feasible flow in the blocking path graph. For the reason that there are some dependent production points in the blocking path graph of a network, the proof about the tenability of the Gale's Theorm for the planat normalized network without circuit is made.
