首页 | 本学科首页   官方微博 | 高级检索  
文章检索
  按 检索   检索词:      
出版年份:   被引次数:   他引次数: 提示:输入*表示无穷大
  收费全文   2篇
  国内免费   2篇
  完全免费   1篇
  数学   5篇
  2016年   2篇
  2014年   1篇
  2011年   2篇
排序方式: 共有5条查询结果,搜索用时 187 毫秒
1
1.
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.  相似文献
2.
This paper deals with the pos/neg-weighted p-median problem on tree graphs where all customers are modeled as subtrees. We present a polynomial algorithm for the 2-median problem on an arbitrary tree. Then we improve the time complexity to O(n log n) for the problem on a balanced tree, where n is the number of the vertices in the tree.  相似文献
3.
A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G. The clique-transversal number, denoted by τ c (G), is the minimum cardinality of a clique-transversal set in G. In this paper we give the exact value of the clique-transversal number for the line graph of a complete graph. Also, we give a lower bound on the clique-transversal number for 4-regular claw-free graphs and characterize the extremal graphs achieving the lower bound.  相似文献
4.
A set S of vertices in a graph G = (V, E) without isolated vertices is a total outer-connected dominating set (TCDS) of G if S is a total dominating set of G and G[V − S] is connected. The total outer-connected domination number of G, denoted by γ tc (G), is the minimum cardinality of a TCDS of G. For an arbitrary graph without isolated vertices, we obtain the upper and lower bounds on γ tc (G) + γ tc ($ \bar G $ \bar G ), and characterize the extremal graphs achieving these bounds.  相似文献
5.
In this note we study the general facility location problem with connectivity. We present an O(np 2)-time algorithm for the general facility location problem with connectivity on trees. Furthermore, we present an O(np)-time algorithm for the general facility location problem with connectivity on equivalent binary trees.  相似文献
1
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号