.png){kind=icon}
返回
Modeling and solving the angular constrained minimum spanning tree problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2019.104775.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Assume one is given an angle alpha is an element of(0, 2 pi] and a complete undirected graph G = (V, E). The vertices in V represent points in the Euclidean plane. The edges in E represent the line segments between these points, with edge weights equal to segment lengths. Spanning trees of G are called alpha-spanning trees (alpha-STs) if, for any i is an element of V, the smallest angle that encloses all line segments corresponding to its i-incident edges does not exceed alpha. The Angular Constrained Minimum Spanning Tree Problem (alpha-MSTP) seeks an alpha-ST with the least weight. The problem arises in the design of wireless communication networks operating under directional antennas. We propose two alpha-MSTP formulations. One, F-x requiring, in principle, O(2(vertical bar V vertical bar)) inequalities to model the angular constraints (alpha-AC). For alpha is an element of(0, pi), however, we show that just O(vertical bar V vertical bar(3)) of them suffice to attain not only a formulation but also the same Linear Programming relaxation (LPR) bound as the full blown model. The other formulation, F-xy, enlarges the set of F-x variables but manages to model alpha-AC, compactly. Furthermore, F-xy LPR bounds are proven to dominate their F-x counterparts. That dominance, however, is empirically shown to reduce as alpha increases. Finally, exact Branch-and-Cut algorithms implemented for the two formulations are shown, empirically, to exchange roles as top performer, throughout the [0, 2 pi) range of alpha values. (C) 2019 Elsevier Ltd. All rights reserved.
Keyword:
Combinatorial optimization
Angular constrained spanning trees
Branch-and-cut algorithms
Polyhedral combinatorics
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
Association between a body shape index and abdominal aortic calcification in general population: A cross-sectional study身体形态指数与腹主动脉钙化在一般人群中的关联：一项横断面研究
OAAI
OAAI分享收藏Injury-Dependent and Disability-Specific Lumbar Spinal Gene Regulation following Sciatic Nerve Injury in the Rat大鼠坐骨神经损伤后损伤依赖性和残疾特异性腰椎基因调控.png)
PLOS ONEOAAI
PLOS ONEIF0
OAAI分享收藏A BRANCH-AND-CUT ALGORITHM FOR THE RESOLUTION OF LARGE-SCALE SYMMETRICAL TRAVELING SALESMAN PROBLEMSSIAM REVIEW
SIAM REVIEWIF6.1
PREAI
分享收藏Association of a body shape index and hip index with cardiometabolic risk factors in children and adolescents: the CASPIAN-V study身体形状指数和臀围指数与儿童及青少年 cardiometabolic 风险因素的相关性：CASPIAN-V 研究
OAAI
OAAI分享收藏 没有更多内容
没有更多内容