多项式时间算法相关论文
针对有向网络中最大容量支撑树形图扩容问题（EMCSA）,由0-1背包问题出发归约出EMCSA问题的一个实例,从而证明EMCSA问题是NP-困难的,并......
排序论又称时间表理论，已经发展成为运筹学的一个重要分支，作为一门应用科学，它有深刻的实际背景和广阔的应用前景。分批排序问题、多......
本文研究了供应链管理中的集成配送和加工的两阶段分批调度问题,在配送阶段,由多辆运输工具将工件从仓储区运送到批处理机进行深加......
排序问题是一类重要的组合最优化问题,也是运筹学研究的一个非常活跃的分支,具有较强的应用背景。机器具有学习效应的排序是一种新......
作为运筹学的一个分支,一门应用科学,排序问题有着深刻的实际背景和广阔的应用前景。在《美国国防部与数学科学研究》的报告中,作......
排序问题作为一门应用科学,是运筹学的一个重要方面。自从Biskup把学习效应应用到排序问题中以来,带有学习效应的排序问题就备受国......
图作为一种常用的数据结构,可以灵活且直观地描述世界上的各种实体以及实体之间繁杂多样的关系,因此被广泛地应用于多个行业和学科......
经过几十年的发展,图的控制参数理论已经成为图论中非常活跃的研究领域之一.基于不同的实际背景,人们提出了许多控制参数.控制参数......
研究单机带有恶化效应的松弛工期窗口排序问题,其中工件的加工时间是一般的线性恶化.对两类目标函数进行研究:一是提前惩罚、误工......
由于排序论在运筹学中的重要性,排序问题从不同的角度引起了越来越多学者的关注.为了让排序问题和现实生活更紧密地联系起来,多代......
排序理论是运筹学组合优化领域中最为活跃的分支之一.自上世纪50年代以来,一直备受生产制造、供应链管理、互联网等领域研究人员的......
顶点覆盖问题是经典的组合最优化问题.顶点带非负权重的顶点覆盖问题在一般图上是NP-难的,而在二部图上却能在多项式时间之内被解......
It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with ......
This paper studies the self-similar fractals with overlaps from an algorithmic point of view.A decidable problem is a qu......
本文研究了生成一个图的全部极大独立集所需的理论，提出了一个实用的生成方法。
In this paper, we study the theory needed to g......
判断任意两个图是否同构的问题是一个很难的问题,至今未找到有效算法.该文给出了判定两个Halin图H、H同构的多项式时间算法.对于其......
该文利用结构分析理论,结合化简技术,分别从控制的角度与合成分解的角度对非对称选择网的主要行为特征--活性（包括有界性）进行了深入......
反馈顶点集是给定图中的一个顶点子集，删除这个顶点子集让剩下的图成为森林。最小反馈顶点集问题是经典的NP完全问题之一，在实践中有......
近年来，无限状态系统的验证成为了一个十分热门的研究领域。其中研究的重要问题不仅仅有对系统间等价的判定，还包括对系统和特定有限......
本论文主要研究2-边染色与2-弧染色重载费用欧拉回路问题。对2-边染色重载费用欧拉回路问题,具体描述如下:给定一个2-边染色欧拉图......
排序(Scheduling)问题在运筹学和组合最优化中占有重要的地位.经典的平行机排序问题是NP-难的.它的一个实例是给定m台平行机,和n个......
限制性K-树问题是一类组合优化问题,它具有重要的理论研究价值和实际应用价值。本论文研究限制性K-树问题的一种推广形式,称之为限......
令G是一个连通的简单图.图G的一个边染色c是将一些颜色分配到图G的边上,而G的一个边赋权w是将一些权重分配到图G的边上.边染色图G......
排序问题是一类重要的组合最优化问题,其目的是利用一些资源,最优地完成一批任务,在实际生活中的很多方面都扮演着很重要的角色.随......
在组合最优化中,装填与覆盖占据一个非常重要的位置.给定一个图,一组边不交的集合称为匹配,一组与图中所有边都关联的顶点的集合称......
开发高效、精确的排序算法是组合优化中的一个重要课题.通过确定排序策略,可以在有限的资源和各种约束条件下,优化所选择的性能指......
本文利用了3-状态设备网络可靠度计算转化为2-状态网络可靠度计算的一个归约定理,结合J.Scott Provan等的算法,给出计算3-状态设备......
六、NP—完全问题在前面所述的问题分类中,“已证明是不可解的问题类及已证明是难解的问题类”,我们不必去研究了。对于“已证明......
已经证明攻破由作者提出的公开密钥密码体制如同分解大数一样困难。本文论述要推出明文第K个最小有效位也就象因子分解一样困难(这......
本文提出了采用倒数的公开密钥密码体制。攻破所提出的这种密码体制就象分解大数一样困难。
This paper presents a public key c......
本文提出了陷阱区间的定义,分析了陷阱点的结构,估计了陷阱点的测度,对Shamir提出的多项式时间算法进行了分析与讨论。
This pape......
本文考虑目标函数为Lmax和∑ωjCj的单机上批容量无限制的两类双目标分批排序模型：约束模型和线性加权模型。这里通过动态规划的递......
本文首先回顾了部分密钥托管思想和部分可验证的密钥托管思想,并提出了部分可验证性和独立性的重要性.如果能在多项式时间内从托管......
本文基于逻辑代数的反向运算和对自变元的等级划分规则给出了一种分级赋值求解SAT问题的多项式时间算法.这种方法根据逻辑代数中基......
本文提出了一种基于XML的数据交换中的函数依赖转换方法,具体包括:运用外键连接与路径转换规则来转换关系模式,生成相应的XML模式,......
该文对单机作业下ｎ个任务确定最优公共交货期和最优加工顺序。目标函数考虑了提前／拖期惩罚（提前／拖期惩罚系数不同的情况）和附加惩罚（交......
该文研究了单机作业下ｎ个任务折调度问题，假设如果任务在交货期准时完工，则不受惩罚；如果任务的完成时间偏离了顾客所设置的交货期，就要......
该文讨论了瓶颈指派问题的三种算法：化为经典指派问题法，拟枚举法和阀门算法，其中第三种方法是该文作者利用Ｄ·Ｋｏｎｉｇ定理对原阀门算法的改进......
本文介绍了知识库更新的基本概念及命题知识库更新的复杂性研究现状．近年来，学者们提出了许多方法进行命题知识库的更新，一类是基于公......
选址理论研究的是在特定的区域内为服务设施(或供给点)如配送中心，消防队，急救中心，工厂等选择一个最优的地址，其数学模型取决于可选址......
本文主要对几类Steiner树问题进行了详细的论述。欧氏平面上的Steiner树问题是这样描述的，在欧氏平面内给定一个点集，连接这些点的最......
最小支撑树形图问题是一类经典的组合优化问题，我们分别有朱-刘算法和Edm-onds算法来解决。本论文主要研究在有向图上支撑树形图的......
最小支撑树形图问题是一类经典的组合优化问题,我们已经有朱-刘算法或Edmonds算法来解决。本论文主要研究有向网络中最大容量树形......
