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.展开更多
文摘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.
