固定顶点的树划分问题

来源 :云南大学学报：自然科学版 | 被引量 : 0次 | 上传用户：kaka43210

【摘要】

：

考虑了2个固定顶点的树划分问题,即固定k个顶点的最小和树划分问题和固定k个顶点的最小最大树划分问题,我们得到如下结果:①利用Greedy技巧,得到固定k个顶点的最小和树划分问

【作者】

：

张同全王泽磊李建平

【机构】

：

云南大学

【出处】

：

云南大学学报：自然科学版

【发表日期】

：

2005年1期

【关键词】

：

顶点多项式算法近似算法证明 NP 最优固定问题技巧利用 anti-cycle k-approximate algorithm minimal sp

【基金项目】

：

国家自然科学基金，云南省自然科学基金

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

考虑了2个固定顶点的树划分问题,即固定k个顶点的最小和树划分问题和固定k个顶点的最小最大树划分问题,我们得到如下结果:①利用Greedy技巧,得到固定k个顶点的最小和树划分问题的最优多项式算法;②证明了固定k个顶点的最小最大树划分问题是NP-难的,并利用①的结果给出了固定k个顶点的最小最大树划分问题的一个k-近似算法.

其他文献

一类解耦双曲守恒律系统的狄拉克激波

研究一类解耦的具有线性退化特征的非严格或严格双曲守恒律系统的黎曼问题．借助特征分析方法，在广义Rankine-Hugoniot条件和熵条件下，获得该问题的狄拉克激波解．

期刊

双曲守恒律系统狄拉克激波(δ-激波)广义Rankine-Hugoniot条件熵条件hyperbolic system of conservation l

含有2个参数的非线性四阶边值问题解的一个存在定理

通过选择适当的Banach空间并且利用Leray—Schauder非线性抉择，对含有2个参数及各阶导数一类非线性四阶两点边值问题建立了一个存在定理．在此项工作中，非线性项满足某种函数型线

期刊

四阶常微分方程两点边值问题非线性存在性fourth-order ordinary differential equation two-point bo

基于正交表的支持向量机并行学习算法

对大规模训练样本的支持向量机训练问题进行探索,提出了一种基于正交表的并行学习算法.这种方法通过求解一些相互独立的小的训练问题来求解大的训练问题,采用多处理机可求解

期刊

正交表并行计算SVMHBSVMorthogonal array parallel compute support vector machine （S

基于变量逐步选择的Bayes信用风险判别模型

应用逐步判别理论筛选模型自变量,建立Bayes判别函数,推导出具体的判别模型.实证分析显示,模型具有良好的分辨精度.考虑到模型的应用范围,变量筛选时舍弃了上市公司特有的一

期刊

信用风险Wilks统计量Bayes判别函数credit risk Wilks Lambda Bayes discriminant function

一类非线性悬臂梁方程解的存在性

考察了1类非线性悬臂梁方程．在力学上，这类方程描述了1端固定，另1端自由的弹性梁的形变．本文中方程的特点是非线性项含有未知函数的三阶导数．通过使用方程的分解技巧和Leray-Sehau

期刊

非线性常微分方程两点边值问题解和正解存在性不动点定理nonlinear ordinary differential equation two-poi

3种嵌入式操作系统内核的关键技术分析

内核是操作系统的核心组成部分．其中,任务管理、进程的同步和通信机制、存储器管理等是内核实现的关键技术．对μC/OS-Ⅱ,Windows CE和嵌入式Linux 3种嵌入式操作系统的内核关键

期刊

嵌入式操作系统μC/OS-ⅡWindowsCE嵌入式LINUXembedded systemμC/OS-Ⅱ Windows CE embedde

Quantile第Ⅰ类分布的参数估计

Quantile第Ⅰ类分布是一类为克服经典分布在拟合金融收益率数据表现不佳而提出来的新分布族,其拥有的可变尾部厚度、独立变化的左右尾厚度及显示的分位数函数等特性,使其在拟

期刊

Quantile第Ⅰ类分布极大似然估计大样本性质厚尾分布不对称分布Quantile Class I distribution MLE Large

非双倍测度下参数型Marcinkiewicz积分多线性交换子的有界性

在参数型Marcinkiewicz积分Mρ的核函数满足较强的H？rmander条件下,利用非双倍测度的特性,证明了参数型Marcinkiewicz积分与Lipschitz函数生成的多线性交换子Mbρ（f）在非双倍测

期刊

非双倍测度参数型MARCINKIEWICZ积分MORREY空间有界性non-doubling parameter Marcinkiewicz inte

最优投资消费问题的对偶解法

考虑了市场中投资者信息的不对称性。用Lagrange乘数法给出了一类最优投资消费问题的对偶问题，并给出了该问题在完备市场下的最优解．对于不完备市场，讨论了最优解的存在性和唯一

期刊

投资消费策略最优解效用函数滤子凸对偶investment policies with consumption optimal solution u

贫困大学生心理障碍及其矫正研究

由于受到经济贫困状况的影响,贫困大学生群体出现自卑、焦虑、孤僻、焦虑等心理障碍高发的现象,严重影响到了该群体的心理健康。建立有效的心理干预矫正机制,加强对贫困大学

期刊

贫困大学生心理障碍矫正

固定顶点的树划分问题

与本文相关的学术论文