排序方式： 共有3条查询结果，搜索用时 0 毫秒
1
1.
研究了在3种情况下直线上的区间图的最小连通控制集的计算问题:(1)相交于一点的直线簇;(2)除一条直线外,其余的直线都平行的直线簇;(3)一条直线和直线上t个赋权的点,使得其最小连通控制集所覆盖的点的权和最大.给出了这3个问题的多项式时间算法,问题1和问题2可以在O(n)时间内求解,借助动态规划方法问题3可以在O(n+t)时间内求解. 相似文献
2.
研究了广义区间图的最小全控制集和最小配对控制集的计算问题.对有一个公共交点的直线簇上的区间图,给出了计算其最小全控制集的O(n)时间算法和其最小配对控制集的O(n+m)时间算法. 相似文献
3.
有向网络上单源多汇的最优连接问题 总被引：1，自引：0，他引：1
以信息需求系统为背景,研究有向网络上从一个顶点到若干顶点的连接方式,使总的连线长度为最小.这是最短路问题的推广,使用的方法是基于组合最优化的算法分析,包括NP-困难性及多项式可解情形.关于后一方面,若干约化规则起着重要作用.主要结果是得到序列平行图等典型图类的有效算法和一般图的启发式算法.目前的工作是为处理这样一个难解问题提供了一个基本的途径.更多的结构性质及典型算法值得进一步研究. 相似文献
1