首页> 外文期刊>Algorithmica >Maximum Plane Trees in Multipartite Geometric Graphs
【24h】

Maximum Plane Trees in Multipartite Geometric Graphs

机译:多脚石几何图中的最大平面树

获取原文
获取原文并翻译 | 示例

摘要

A geometric graph is a graph whose vertices are points in the plane and whose edges are straight-line segments between the points. A plane spanning tree in a geometric graph is a spanning tree that is non-crossing. Let R and B be two disjoint sets of points in the plane such that RB is in general position, and let n=|RB|. Assume that the points of R are colored red and the points of B are colored blue. A bichromatic plane spanning tree is a plane spanning tree in the complete bipartite geometric graph with bipartition (R,B). In this paper we consider the maximum bichromatic plane spanning tree problem, which is the problem of computing a bichromatic plane spanning tree of maximum total edge length.For the maximum bichromatic plane spanning tree problem, we present an approximation algorithm with ratio 1/4 that runs in O(nlogn) time.We also consider the multicolored version of this problem where the input points are colored with k2 colors. We present an approximation algorithm that computes a plane spanning tree in a complete k-partite geometric graph, and whose ratio is 1/6 if k=3, and 1/8 if k4.We also revisit the special case of the problem where k=n, i.e., the problem of computing a maximum plane spanning tree in a complete geometric graph. For this problem, we present an approximation algorithm with ratio 0.503; this is an extension of the algorithm presented by Dumitrescu and Toth (Discrete Comput Geom 44(4):727-752, 2010) whose ratio is 0.502.For points that are in convex position, the maximum bichromatic plane spanning tree problem can be solved in O(n3) time. We present an O(n5)-time algorithm that solves this problem for the case where the red points lie on a line and the blue points lie on one side of the line.
机译:几何图是一个图形,其顶点是平面中的点,其边缘是点之间的直线段。几何图中的平面生成树是一个非交叉的生成树。让R和B是平面中的两个不相交的点组,使得RB处于一般位置,并且设为rb |。假设R的点是有色红色,B的点是彩色的蓝色。一架双层跨越树是具有双胞胎(R,B)的完整二角形几何图中的平面跨越树。在本文中,我们考虑了最大的双色平面跨越树问题,这是计算最大总边缘长度的双色平面跨越树的问题。对于最大的双色平面跨越树问题,我们呈现了比率1/4的近似算法在O(nlogn)的时间内运行。我们还考虑其中输入点的多色版本,其中包含k> 2颜色。我们介绍了一种近似算法,该近似算法计算完整的k-passite几何图中的平面生成树,并且其比率为1/6,如果k = 3,1/8,如果k4。我们还重新审视问题的特殊情况= n,即计算完整几何图中的最大平面跨越树的问题。对于这个问题,我们呈现了比率0.503的近似算法;这是Dumitrescu和Toth(离散计算GeoM44(4):727-752,12010)的算法的扩展,其比例为0.502。对于处于凸起位置的点,可以解决最大的双色大跨越树问题在O(n3)时间。我们介绍了一个(n5) - 时间算法,解决了红色点位于线的情况下的这个问题,蓝点位于线的一侧。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号