共查询到19条相似文献,搜索用时 78 毫秒
1.
本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的$p-$中位选址问题($p\geq 2$)可分为两类:即 MWD 和 WMD 模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为$O(n^2)$的多项式时间算法. 相似文献
2.
带投资约束且p不确定的推广p-中位问题 总被引:1,自引:0,他引:1
p-中位问题是设施选址中的一个经典模型,在交通、物流等领域有着广泛应用.在经典p-中位问题的基础上提出一种p不确定的推广p-中位问题,并且加上总投资约束,使得此推广模型更加实用.针对此推广模型,提出三种启发式算法:简单启发式算法、变邻域搜索算法和改进的遗传算法.数值实验结果表明变邻域搜索算法和改进的遗传算法在求解此推广模型时是有效的. 相似文献
3.
The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated. 相似文献
4.
5.
负权最短路问题的新算法 总被引:3,自引:0,他引:3
Bellman-Ford算法自1958年以来一直是负权最短路问题的公认的最好算法之一.1970年,Yen对其进行了改进,理论上可以节省一半的计算量.本文得到了一种比Bellman-Ford算法更加优越的算法.尽管在理论上新算法无法保证完全超越于Yen的改进算法,但在许多情况下需要更少的计算量. 相似文献
6.
7.
本文研究光滑度量测度空间上带权Paneitz算子的闭特征值问题和带权圆盘振动问题,给出Euclid空间、单位球面、射影空间和一般Riemann流形的n维紧子流形的权重Paneitz箅子和带权圆盘振动问题的前n个特征值上界估计.进一步地,本文给出带权Ricci曲率有界的紧致度量测度空间上带权圆盘振动问题的第一特征值的下界... 相似文献
8.
顶点数为n,边数为m的简单图G的非负广义邻接矩阵定义为U(G)=γAA(G)+γII(G)+γJJ(G)+γDD(G),其中γA,γI,γJ,γD是一些非负实数,A(G)是图G的邻接矩阵,D(G)=diag(d1,d2,…,dn),I(G)是单位矩阵,J(G)是全1矩阵.本文得到了谱半径ρU(G)的一些界,并刻画了达到这些界时的极图.此外还得到了ρAα(G)的新界以及ρA(G),ρL(G)和ρQ(G)的已知界. 相似文献
9.
10.
一类带单源约束的选址运输问题算法研究 总被引:1,自引:0,他引:1
带单源约束的选址运输问题是在经典的选址运输问题基础上考虑每个顾客需求的产品仅由一家工厂供应的情况。所建立的模型是整数规划,是NP难的。本文先考虑了开办费用为零的带单源约束的选址运输问题,即带单源约束的运输问题。松弛其中一种变量约束,借鉴求解运输问题的表上作业法,给出了一种修正的表上作业法,然后将算法推广。最后给出了将算法应用在Excel随机生成的测试问题上所得到的结果,与LINDO求得的最优解相比,差距很小。由此得出结论:对规模较小的带单源约束的选址运输问题,本文提出的算法是简便且行之有效的。 相似文献
11.
The interval graph completion problem of a graph G includes two class problems: the profile problem and the pathwidth problem, denoted as P(G) and PW(G) respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI-layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite Graph Kn1,n2,…,nr(r≥2) are determined. 相似文献
12.
We give two structural characterizations of the class of finite intersection graphs of the open and closed real intervals of unit length. This class is a proper superclass of the well‐known unit interval graphs. 相似文献
13.
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. 相似文献
14.
The ferry problem may be viewed as generalizations of the classical wolf-goat-cabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five. 相似文献
15.
设Fk*是满足以下条件的3-正则2-连通平面图G所组成的图类,在G中存在这样的圈C,使得G-E(C)产生k个不相交的树T1,…,Tk(|E(Ti)|≥3,i=1,…,k),且这些树是按C的指定方向C*依次粘在圈C上的.本文主要证明了如下结果:Fk*中的图都是Hamilton的. 相似文献
16.
图G的线性2-荫度la_2(G)是将G分解为k个边不交的森林的最小整数k,其中每个森林的分支树是长度至多为2的路.本文证明了若G是最大度为Δ(G)的K_4-minor-free图,则la_2(G)≤(Δ(G) 5)/2. 相似文献
17.
18.
Les R. Foulds Horst W. Hamacher Anita Schöbel Tadashi Yamaguchi 《Annals of Operations Research》2003,122(1-4):163-175
Finding good cycles in graphs is a problem of great interest in graph theory as well as in locational analysis. We show that the center and median problems are NP-hard in general graphs. This result holds both for the variable cardinality case (i.e., all cycles of the graph are considered) and the fixed cardinality case (i.e., only cycles with a given cardinality p are feasible). Hence it is of interest to investigate special cases where the problem is solvable in polynomial time. In grid graphs, the variable cardinality case is, for instance, trivially solvable if the shape of the cycle can be chosen freely. If the shape is fixed to be a rectangle one can analyze rectangles in grid graphs with, in sequence, fixed dimension, fixed cardinality, and variable cardinality. In all cases a complete characterization of the optimal cycles and closed form expressions of the optimal objective values are given, yielding polynomial time algorithms for all cases of center rectangle problems. Finally, it is shown that center cycles can be chosen as rectangles for bounded cardinalities such that the center cycle problem in grid graphs is in these cases completely solved. 相似文献