检索结果-南通市图书馆

Inverse minimum spanning tree problem and reverse shortest-path problem with discrete values

在线全文

学校读者我要写书评

暂无评论

Progress in Natural Science:Materials International 2006年第6期16卷 649-655页

作者： LIU Longcheng and HE Yong (Department of Mathematics, Zhejiang University, Hangzhou 310027, China State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310027, China) Department of Mathematics Zhejiang University Hangzhou 310027 China State Key Laboratory of CAD and CG Zhejiang University Hangzhou 310027 China

In this paper, we consider two network improvement problems with given discrete values: the inverse minimum spanning tree problem and the reverse shortest-path problem, where the decrements of the weight of the edges are given discrete values. First, for the three models of the inverse minimum spanning tree problem (the sum-type, the bottleneck-type and the constrained bottleneck-type), we present their respective strongly polynomial algorithms. Then, we show that the reverse shortest-path problem is strongly NP-complete.

关键词： minimum spanning tree shortest-path problem inverse problem reverse problem computational complexity.

Investigating the Disparities of China's Insurance Market Based on minimum spanning tree from the Viewpoint of Geography and Enterprise

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of Systems Science and Information 2017年第3期8卷 216-228页

作者： Chi XIE Yingying ZHOU Gangjin WANG Xinguo YAN College of Business Administration Hunan University Center for Finance and Investment Management Hunan University Center for Polymer Studies and Department of Physics Boston University

In this paper, we investigate the disparities of China’s insurance market from the viewpoint of geography and enterprise by using the monthly data from January 2006 to December 2015. We divide the whole insurance market into two parts, namely property insurance and personal *** constructing and analyzing minimum spanning trees of insurance market, we obtain the results as follows:(i) The connections between provinces are much closer than those of firms, and there are regional links between neighboring provinces in the minimum spanning tree(MST); and(ii) the domestic funded firms and foreign funded firms form two explicit clusters in the MSTs of property and personal insurance market.

关键词： network analysis minimum spanning tree China's insurance market disparity province-level firm-level

On the minimum spanning tree Determined by n Points in the Unit Square

在线全文

学校读者我要写书评

暂无评论

Chinese Quarterly Journal of Mathematics 1999年第2期14卷 76-82,页

作者：叶继昌徐寅峰徐成贤 Xi’an

Let P n be a set of n points in the unit square S,l(P n) denoe the length of the minimum spanning tree of P n, andC n= max P nSl(P n), n=2,3,… In this paper,the exact value of C n for n=2,3,4 and the corres... 详细信息

关键词： minimum spanning tree maximin problem configuration

ON THE INVERSE minimum spanning tree PROBLEM WITH minimum NUMBER OF PERTURBED EDGES

在线全文

学校读者我要写书评

暂无评论

Systems Science and Systems Engineering 2003年第3期12卷 350-359页

作者： BangyiLI ZhaohanSHENG CollegeofEconomicsandManagement NanjingUniversityofAeronauticsandAstronauticsNanjing210016China GraduateSchoolofManagementScienceandEngineering NanjingUniversityNanjing210093China

Let G= be a network with the vertex set V, the edge set E and the length vector L, and let T* be a prior determined spanning tree of G. The inverse minimum spanning tree problem with minimum number of perturbed edges is to perturb the length vector L to L+ , such that T* is one of minimum spanning trees under the length vector L+ and the number of perturbed edges is minimum. This paper establishes a mathematical model for this problem and transforms it into a minimum vertex covering problem in a bipartite graph G0, a path-graph. Thus a strongly polynomial algorithm with time complexity O(mn2) can be designed by using Hungarian method.

关键词： Inverse network optimization problem minimum spanning tree vertex covering set

Finding Cut-Edges and the minimum spanning tree via Semi-Tensor Product Approach

在线全文

学校读者我要写书评

暂无评论

Journal of Systems Science and Information 2018年第5期9卷 459-472页

作者： Xujiao FAN Yong XU Xue SU Jinhuan WANG School of Science Hebei University of Technology

Using the semi-tensor product of matrices, this paper investigates cycles of graphs with application to cut-edges and the minimum spanning tree, and presents a number of new results and algorithms. Firstly, by defining a characteristic logical vector and using the matrix expression of logical functions, an algebraic description is obtained for cycles of graph, based on which a new necessary and sufficient condition is established to find all cycles for any graph. Secondly, using the necessary and sufficient condition of cycles, two algorithms are established to find all cut-edges and the minimum spanning tree, respectively. Finally, the study of an illustrative example shows that the results/algorithms presented in this paper are effective.

关键词： semi-tensor product cycle cut-edge minimum spanning tree

Degree-Constrained minimum spanning tree Problem of Uncertain Random Network

在线全文

学校读者我要写书评

暂无评论

Degree-Constrained Minimum Spanning Tree Problem of Uncertai...

Lot Release Strategy Semiconductor Assembly and Testing Based on The Degree of Constraint of The minimum spanning tree

第十四届中国不确定系统年会第十八届中国青年信息与管理学者大会

作者： Lifen Jia Xin Gao School of Mathematical Sciences and Physics North China Electric Power University

The degree-constrained minimum spanning tree(DCMST) problem is to find the least weight spanning tree of a given network, subject to constraints on node *** paper firstly investigates the DCMST problem of uncertain random network in which some weights are uncertain variables and others are random variables. A concept of ideal chance distribution of DCMST problem is proposed here. For seeking the degree-constrained spanning tree which is closest to the ideal chance distribution, an uncertain random programming model is formulated here to find the ***, a numerical example is provided to illustrate its effectiveness.

关键词： minimum spanning tree uncertain random network chance theory

来源： cnki会议评论

在线全文

cnki会议

学校读者我要写书评

暂无评论

Lot Release Strategy Semiconductor Assembly and Testing Base...

Fuzzy Quadratic minimum spanning tree Problem

第26届中国控制与决策会议

作者： Zhang Guohui Liu Chang Yao Lili Shi Haibo SHENYANG INSTITUTE OF AUTOMATION CHINESE ACADEMY OF SCIENCES

The production of semiconductor assembly and testing is wide variety,and the cost of produce time of switch between different products is not the same,which could lead to its utilization is lower,production cycle *** lot release control plays an important role for improving utilization and shorter production cycle for semiconductor assembly and testing *** this paper,we modeled as a graph theory for solving constrained minimum spanning tree *** mainstream Prim algorithm,we solve it to give each product sequence and specific lot release *** have solved the extra time problem that caused by blinding lot release,and finally,through applied research we verified the effectiveness and superiority of *** proposed strategy can reduce the change machine costs,shorten production cycle and improve production efficiency.

关键词： semiconductor assembly and testing graph theory minimum spanning tree Prim algorithm

来源： cnki会议评论

在线全文

cnki会议

学校读者我要写书评

暂无评论

Fuzzy Quadratic Minimum Spanning Tree Problem

minimum spanning trees Across Well-Connected Cities and with Location-Dependent Weights

第二届不确定系统年会

作者： Jinwu Gao Mei Lu Uncertainty Theory Laboratory, Department of Mathematical Sciences Tsinghua University, Beijing 100084, China

In this paper, a fuzzy quadratic minimum spanning tree problem is formulated as expected value model, chance-constrained programming and dependent-chance programming according to different decision criteria. Then the crisp equivalents are derived when the fuzzy costs are characterized by trapezoidal fuzzy numbers. Furthermore, a simulation-based genetic algorithm using Prufer number representation is designed for solving the proposed fuzzy programming models as well as their crisp equivalents. Finally, a numerical example is provided for illustrating the effectiveness of the genetic algorithm.

关键词： minimum spanning tree fuzzy programming genetic algorithm credibility measure

来源： cnki会议评论

在线全文

cnki会议

学校读者我要写书评

暂无评论

Communications in Mathematics and Statistics 2022年第1期10卷 1-50页

作者： Ghurumuruhan Ganesan Institute of Mathematical Sciences HBNIChennaiIndia

Consider n nodes{X_(i)}_(1≤i≤n) independently and identically distributed(i.i.d.)across N cities located within the unit square *** city is modelled as an r_(n)×r_(n)square,and MSTC_(n)denotes the weighted length of the minimum spanning tree containing all the n nodes,where the edge length between nodes X_(i)and X_(j)is weighted by a factor that depends on the individual locations of X_(i)and X_(j).We use approximation methods to obtain variance estimates for MSTC_(n)and prove that if the cities are well connected in a certain sense,then MSTC_(n)appropriately centred and scaled converges to zero in *** the above proof techniques we also study MST_(n),the length of the minimum weighted spanning tree for nodes distributed throughout the unit square S with location-dependent edge *** this case,the variance of MST_(n)grows at most as a power of the logarithm of n and we use a subsequence argument to get almost sure convergence of MST_(n),appropriately centred and scaled.

关键词： minimum spanning tree Well-connected cities Location-dependent edge weights