直线簇上区间图的最小连通控制集

来源 :上海大学学报:自然科学版 | 被引量 : 0次 | 上传用户:lihaidong2000
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
研究了在3种情况下直线上的区间图的最小连通控制集的计算问题:(1)相交于一点的直线簇;(2)除一条直线外,其余的直线都平行的直线簇;(3)一条直线和直线上t个赋权的点,使得其最小连通控制集所覆盖的点的权和最大.给出了这3个问题的多项式时间算法,问题1和问题2可以在O(n)时间内求解,借助动态规划方法问题3可以在O(n+t)时间内求解.
其他文献
动态失速是限制相关机械或飞行器性能的重要因素,因而对动态失速控制的研究具有重要的工程意义。以二维非定常可压RANS方程为控制方程,采用Jameson中心有限体积法,对攻角作α=15
该文介绍了一个基于单片数字信号处理器的8路语音卡的设计方案,阐述了C6211 DSP(数字信号处理器)芯片的优点及其与外围电路的接口方法,并给出了系统的软件编程流程;简要地介
以Zr-4为母合金,分别添加电解纯铜或电解金属锰,用非自耗真空电弧炉熔炼了成分不同的6种锆合金.用透射电子显微镜观察了合金中第二相的形貌,用EDS分析了第二相的成分,用SAD确定了
大学校长是大学的灵魂,为了领导与管理好大学,大学校长应具备人格权威、专业学术权威、行政职务权威与管理权威相协调的、合理的权威结构,避免缺少某种权威或滥用某种权威的不合
目的:观察优质护理在冠心病护理中的效果。方法选取200例冠心病患者,随机分为常规护理组和优质护理组,各100例。常规护理组患者给予常规护理,优质护理组患者给予优质护理,比较两组
应用灰色关联分析研究了青海秦艽药材指纹图谱之间的相关性.以秦艽指纹图谱的实验数据研究了灰色关联度、相关系数和夹角余弦的优劣.相关系数和夹角余弦对数据的差异不够敏感,灰
目的探讨妇产科急诊患者心理问题的形成原因及护理对策。方法将我院收治的妇产科急诊患者280例采取自然观察法、交谈法以及问卷调查法进行心理问题评估,并对患者心理问题的诱
该文研究的是一种新型的基于同步齿型带的差动直线运动机构.该机构是在传统的同步带机构的主、从动轮之间加上一套由大小不同的两个同轴固联在一起的差动轮组成的差动传动机
目的观察甲硝唑联合左氧氟沙星与山莨菪碱治疗慢性肠炎的疗效,为慢性肠炎的治疗提供依据。方法选择2010年1月~2014年10月在我院接受治疗的慢性肠炎患者68例,按照随机数字表法
目的探讨急性脑梗塞所致颅内高压的特点及其治疗方法,并进行分析,以供参考。方法选取2013年7月-2014年6月我院收治的急性脑梗塞所致颅内高压患者54例作为研究对象。并将其随机