首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 109 毫秒
1.
Given an edge weighted graph, the maximum edge-weight connected graph (MECG) is a connected subgraph with a given number of edges and the maximal weight sum. Here we study a special case, i.e. the Constrained Maximum Edge-Weight Connected Graph problem (CMECG), which is an MECG whose candidate subgraphs must include a given set of k edges, then also called the k-CMECG. We formulate the k-CMECG into an integer linear programming model based on the network flow problem. The k-CMECG is proved to be NP-hard. For the special case 1-CMECG, we propose an exact algorithm and a heuristic algorithm respectively. We also propose a heuristic algorithm for the k-CMECG problem. Some simulations have been done to analyze the quality of these algorithms. Moreover, we show that the algorithm for 1-CMECG problem can lead to the solution of the general MECG problem.  相似文献   

2.
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.  相似文献   

3.
Given a connected graph G=(V,E)with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree(PCST)problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c+e]while taking risk(c+e xe)/(c+e c e)of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p+v]for its inclusion in T while taking risk(yv p v)/(p+v p v)of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.  相似文献   

4.
Let G be an arbitrary spanning subgraph of the complete graph Kr+1 on r+1 vertices and Kr+1-E(G) be the graph obtained from Kr+1 by deleting all edges of G.A non-increasing sequence π=(d1,d2,...,dn) of nonnegative integers is said to be potentially Kr+1-E(G)-graphic if there is a graph on n vertices that has π as its degree sequence and contains Kr+1-E(G) as a subgraph.In this paper,a characterization of π that is potentially Kr+1-E(G)-graphic is given,which is analogous to the Erdo s–Gallai characterization of graphic sequences using a system of inequalities.This is a solution to an open problem due to Lai and Hu.As a corollary,a characterization of π that is potentially Ks,tgraphic can also be obtained,where Ks,t is the complete bipartite graph with partite sets of size s and t.This is a solution to an open problem due to Li and Yin.  相似文献   

5.
图的循环带宽和   总被引:1,自引:0,他引:1  
Abstract. Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.  相似文献   

6.
张振坤  余敏 《数学季刊》2015,(2):308-316
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.  相似文献   

7.
Let G be an edge-colored graph.The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G.In the authors' previous work,it has been proved that the problem is NP-complete and there does not exist any constant factor approximation algorithm for it unless P=NP.In this paper the authors show that for any fixed integer r≥5,if the edges of a graph G are colored by r colors,called an r-edge-colored graph,the problem remains NP-complete.Similar result holds for the monochromatic path(cycle)partition problem.Therefore,to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting. A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.  相似文献   

8.
Mesh segmentation is one of the important issues in digital geometry processing. Region growing method has been proven to be a efficient method for 3D mesh segmentation. However, in mesh segmentation, feature line extraction algorithm is computationally costly, and the over-segmentation problem still exists during region merging processing. In order to tackle these problems, a fast and efficient mesh segmentation method based on improved region growing is proposed in this paper. Firstly, the dihedral angle of each non-boundary edge is defined and computed simply, then the sharp edges are detected and feature lines are extracted. After region growing process is finished, an improved region merging method will be performed in two steps by considering some geometric criteria. The experiment results show the feature line extraction algorithm can obtain the same geometric information fast with less computational costs and the improved region merging method can solve over-segmentation well.  相似文献   

9.
Let G be a weighted hypergraph with edges of size i for i = 1, 2. Let wi denote the total weight of edges of size i and α be the maximum weight of an edge of size 1. We study the following partitioning problem of Bollob′as and Scott: Does there exist a bipartition such that each class meets edges of total weight at least (w_1-α)/2+(2w_2)/3? We provide an optimal bound for balanced bipartition of weighted hypergraphs, partially establishing this conjecture. For dense graphs, we also give a result for partitions into more than two classes.In particular, it is shown that any graph G with m edges has a partition V_1,..., V_k such that each vertex set meets at least(1-(1-1/k)~2)m + o(m) edges, which answers a related question of Bollobás and Scott.  相似文献   

10.
A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost ofcompletion times and the cost of compression. The complexity of this problem is still unknown.In Part Ⅱ of this paper,the authors have considered a special case where the compression timesand the compression costs are equal among all jobs. Such a problem appears polynomiafiy solvable by developing an O(n^2) algorithm. In this part(Part Ⅱ ),a general case where the controllable processing times and the compression costs are not equal is discussed. Authors proposehere two heuristics with the first based on some previous work and the second based on the algorithm developed in Part Ⅱ . Computational results are presented to show the efficiency and therobustness of these heuristics.  相似文献   

11.
This paper addresses the robust spanning tree problem with interval data, i.e. the case of classical minimum spanning tree problem when edge weights are not fixed but take their values from some intervals associated with edges. The problem consists of finding a spanning tree that minimizes so-called robust deviation, i.e. deviation from an optimal solution under the worst case realization of interval weights. As it was proven in Kouvelis and Yu (Robust Discrete Optimization and Its Applications, Kluwer Academic, Norwell, 1997), the problem is NP-hard, therefore it is of great interest to tackle it with some metaheuristic approach, namely simulated annealing, in order to calculate an approximate solution for large scale instances efficiently. We describe theoretical aspects and present the results of computational experiments. To the best of our knowledge, this is the first attempt to develop a metaheuristic approach for solving the robust spanning tree problem.  相似文献   

12.
本文针对传统的基于边的最小支撑树逆问题,提出了一类基于点边更新策略的最小支撑树逆问题.更新一个点是指减少与此点相关联的某些边的权值.根据是否含有更新点的费用,考虑了两类模型,它们均可转化为森林上的最小(费用)点覆盖的求解问题,算法的复杂性都是O(mn),其中m=|E|n=|V|。  相似文献   

13.
本在无向网络中,建立了带有边集限制的最均匀支撑树问题的网络模型.中首先解决最均匀支撑树问题,并给出求无向网络中最均匀支撑树的多项式时间算法;然后,给出了求无向网络中带有边集限制的最小树多项式时间算法;最后,在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题.  相似文献   

14.
This paper deals with a minimum spanning tree problem where each edge cost includes uncertainty and importance measure. In risk management to avoid adverse impacts derived from uncertainty, a d-confidence interval for the total cost derived from robustness is introduced. Then, by maximizing the considerable region as well as minimizing the cost-importance ratio, a biobjective minimum spanning tree problem is proposed. Furthermore, in order to satisfy the objects of the decision maker and to solve the proposed model in mathematical programming, fuzzy goals for the objects are introduced as satisfaction functions, and an exact solution algorithm is developed using interactive decision making and deterministic equivalent transformations. Numerical examples are provided to compare our proposed model with some previous models.  相似文献   

15.
This paper is concerned with a special case of the generalized minimum spanning tree problem. The problem is defined on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to find a tree of minimum cost containing at least one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance defines the edge cost. We prove that the problem is strongly -hard even in the case of a special structure of the clustering called grid clustering. We construct an exact exponential time dynamic programming algorithm and, based on this dynamic programming algorithm, we develop a polynomial time approximation scheme for the problem with grid clustering.  相似文献   

16.
In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case performance ratio where n is the number of vertices in G and Δ* is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the analysis is based on novel properties of the edge ranking of trees.  相似文献   

17.
Paths, trees and matchings under disjunctive constraints   总被引:1,自引:0,他引:1  
We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.  相似文献   

18.
On the inverse problem of minimum spanning tree with partition constraints   总被引:5,自引:0,他引:5  
In this paper we first discuss the properties of minimum spanning tree and minimum spanning tree with partition constraints. We then concentrate on the inverse problem of minimum spanning tree with partition constraints in which we need to adjust the weights of the edges in a network as less as possible so that a given spanning tree becomes the minimum one among all spanning trees that satisfy the partition restriction. Based on the calculation of maximum cost flow in networks, we propose a strongly polynomial algorithm for solving the problem.The author gratefully acknowledges the partial support of Croucher Foundation.  相似文献   

19.
Connection problems in mountains and monotonic allocation schemes   总被引:1,自引:0,他引:1  
Directed minimum cost spanning tree problems of a special kind are studied, namely those which show up in considering the problem of connecting units (houses) in mountains with a purifier. For such problems an easy method is described to obtain a minimum cost spanning tree. The related cost sharing problem is tackled by considering the corresponding cooperative cost game with the units as players and also the related connection games, for each unit one. The cores of the connection games have a simple structure and each core element can be extended to a population monotonic allocation scheme (pmas) and also to a bi-monotonic allocation scheme. These pmas-es for the connection games result in pmas-es for the cost game.  相似文献   

20.
We consider the minimum diameter spanning tree problem under the reload cost model which has been introduced by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: Minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85]. In this model an undirected edge-coloured graph G is given, together with a nonnegative symmetrical integer matrix R specifying the costs of changing from a colour to another one. The reload cost of a path in G arises at its internal nodes, when passing from the colour of one incident edge to the colour of the other. We prove that, unless P=NP, the problem of finding a spanning tree of G having a minimum diameter with respect to reload costs, when restricted to graphs with maximum degree 4, cannot be approximated within any constant α<2 if the reload costs are unrestricted, and cannot be approximated within any constant β<5/3 if the reload costs satisfy the triangle inequality. This solves a problem left open by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73-85].  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

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