检索结果-内蒙古大学图书馆

中国科学：数学 2024年第11期54卷 1905-1924页

作者：张一枭李恒侯建锋福州大学离散数学与理论计算机科学研究中心福州350108

不同于图的情形,对于正整数r≥3和一些经典的r-一致超图族M,顶点数固定条件下边数最多的不含M的r-一致超图(称为M的极图)可能不止一个,而且这些超图在距离上相距较远,这种现象被称为不稳定性,也是确定此类超图Turán数的基本障碍.Li... 详细信息

不同于图的情形,对于正整数r≥3和一些经典的r-一致超图族M,顶点数固定条件下边数最多的不含M的r-一致超图(称为M的极图)可能不止一个,而且这些超图在距离上相距较远,这种现象被称为不稳定性,也是确定此类超图Turán数的基本障碍.Liu和Mubayi(2022)给出了第一个具有不稳定性的3-一致超图族的例子.对于r≥4,通过具有不稳定性的3-一致超图族可以构造具有同样性质的r-一致超图族.本文构造第一个不依赖于3-一致超图的4-一致超图族M,使得M有两个在距离上相距较远的极图.同时,本文证明相应的Andrásfai-Erd?os-Sós型稳定性定理:任意最小度接近于极图平均度的不含M的4-一致超图一定是这两个极图中一个的子图.此外,作为本文结果的推论,本文还证明了M的可行域具有两个最大值点.

关键词：超图 Turán数稳定性可行域

来源：评论

学校读者我要写书评

暂无评论

不具有稳定性质的4-一致超图族献给刘桂真教授80华诞

引用

中国科学:数学 2024年

作者：张一枭李恒侯建锋福州大学离散数学与理论计算机科学研究中心

不同于图的情形,对于正整数r3和一些经典的r-一致超图族M,顶点数固定条件下边数最多的不含M的r-一致超图(称为M的极图)可能不止一个,而且这些超图在距离上相距较远,这种现象被称为不稳定性,也是确定此类超图Turán数的基本障碍. Liu... 详细信息

不同于图的情形,对于正整数r3和一些经典的r-一致超图族M,顶点数固定条件下边数最多的不含M的r-一致超图(称为M的极图)可能不止一个,而且这些超图在距离上相距较远,这种现象被称为不稳定性,也是确定此类超图Turán数的基本障碍. Liu和Mubayi (2022)给出了第一个具有不稳定性的3-一致超图族的例子.对于r4,通过具有不稳定性的3-一致超图族可以构造具有同样性质的r-一致超图族.本文构造第一个不依赖于3-一致超图的4-一致超图族M,使得M有两个在距离上相距较远的极图.同时,本文证明相应的Andrásfai-Erd?s-Sós型稳定性定理:任意最小度接近于极图平均度的不含M的4-一致超图一定是这两个极图中一个的子图.此外,作为本文结果的推论,本文还证明了M的可行域具有两个最大值点.

关键词：超图 Turán数稳定性可行域

来源：评论

学校读者我要写书评

暂无评论

基于再聚类和离散优化的k路划分算法

引用

计算机辅助设计与图形学学报 2024年第3期36卷 473-484页

作者：潘萍梅刘欣恬李兴权朱文兴福州大学离散数学与理论计算机科学研究中心福州350116 福州大学数学与统计学院福州350116 鹏城实验室深圳518073 闽南师范大学数学与统计学院漳州363000

为了寻得集成电路更优的k路划分,提出将再聚类和离散优化应用于k路划分算法.首先利用再聚类缩小超图规模,即根据给定划分计算顶点间的评级函数值,依据取值大小进行顶点聚类;然后将超图转换为星型图,并将k路划分问题转换为无约束的离散... 详细信息

为了寻得集成电路更优的k路划分,提出将再聚类和离散优化应用于k路划分算法.首先利用再聚类缩小超图规模,即根据给定划分计算顶点间的评级函数值,依据取值大小进行顶点聚类;然后将超图转换为星型图,并将k路划分问题转换为无约束的离散优化问题;进而设计一个算法迭代移动增益值最大的顶点,在算法求解过程中放宽平衡约束,允许暂时处于不可行域的解,扩大问题的求解空间.在同一平台上使用ISPD98电路测试基准对所提算法、hMETIS-Kway和KaHyPar-K进行测试,并比较最小割值和运行时间.实验结果表明该算法优于hMETIS-Kway,特别是在k=2时,最小割值减少了0.173,速度提升了0.706.此外,该算法对KaHyPar-K也有相应的改进效果.

关键词： k路划分最小割超图聚类离散优化

来源：评论

学校读者我要写书评

暂无评论

集成电路二划分的一维泊松方程方法

引用

福州大学学报（自然科学版） 2023年第6期51卷 749-755页

作者：余永昕潘萍梅朱文兴福州大学离散数学与理论计算机科学研究中心福建福州350108

将集成电路二划分问题转化为等价的一维离散布局问题,在全局布局阶段将问题松弛为连续布局问题,并推导得到一维显式泊松方程.以线长作为目标函数,由泊松方程建立的密度函数作为罚函数,使用非线性优化方法得到全局布局阶段的连续解.在合... 详细信息

将集成电路二划分问题转化为等价的一维离散布局问题,在全局布局阶段将问题松弛为连续布局问题,并推导得到一维显式泊松方程.以线长作为目标函数,由泊松方程建立的密度函数作为罚函数,使用非线性优化方法得到全局布局阶段的连续解.在合法化阶段将连续解映射至原问题的离散解空间,得到原问题的可行解.在详细布局阶段使用FM(factorization machines)算法对离散解进行局部优化,得到最终解.上述二划分方法在ISPD98标准测试样例中的表现相较于传统FM算法,割边减少约36%.将上述方法嵌入多级划分框架KaHyPar,割边约减少7%.

关键词：集成电路二划分多级框架泊松方程集成电路布局

来源：评论

学校读者我要写书评

暂无评论

非负约束稀疏优化问题的一个等价性条件

引用

运筹学学报 2022年第1期26卷 43-59页

作者：吕亚星韩美佳黄子麟朱文兴福州大学数学与统计学院福州大学离散数学与理论计算机科学研究中心

加权l最小化是稀疏优化的主流方法之一。本文对带非负约束的l最小化问题与加权l最小化问题的解之间的关系进行了研究,给出了加权l最小化问题的约束矩阵和目标函数的系数是“s-权优”的定义,并通过该定义给出了加权l最小化问题的解是带... 详细信息

加权l最小化是稀疏优化的主流方法之一。本文对带非负约束的l最小化问题与加权l最小化问题的解之间的关系进行了研究,给出了加权l最小化问题的约束矩阵和目标函数的系数是“s-权优”的定义,并通过该定义给出了加权l最小化问题的解是带非负约束的l最小化问题的解的条件。进一步,本文给出了“s-权优”的充分条件及其具体表示形式,并对其上下界进行了可计算的有效估计。

关键词：线性规划非负稀疏解误差分析等价性条件

来源：评论

学校读者我要写书评

暂无评论

超图中超星不交并的Turán数

引用

数学理论与应用 2023年第1期43卷 64-73页

作者：邓静华侯建锋曾庆厚张一枭福州大学离散数学与理论计算机科学研究中心福州350003

给定一个r一致超图F,F的Turán数exr(n,F)表示n个顶点不含F作为子图的r一致超图的最大边数.当r≥3时,确定exr(n,F)是一件非常困难的事情,尤其是当exr(n,F)=o(n^(r))时.对于一个图F,F的扩张F^(+)是指在图F的每条边上添加r−2个新的点... 详细信息

给定一个r一致超图F,F的Turán数exr(n,F)表示n个顶点不含F作为子图的r一致超图的最大边数.当r≥3时,确定exr(n,F)是一件非常困难的事情,尤其是当exr(n,F)=o(n^(r))时.对于一个图F,F的扩张F^(+)是指在图F的每条边上添加r−2个新的点所得到的r一致超图;F的Berge超图BergeF是一个r一致超图H,满足V(F)⊆V(H)并且存在一个从E(F)到E(H)的双射f,使得对于每个e∈E(F),e⊆f(e).在本文中,我们确定超图中超星不交并的扩张及其Berge超图的Turán数,这是Khormali和Palmer[14]的结果的推广.

关键词： Turán数星扩张 Berge超图

来源：评论

学校读者我要写书评

暂无评论

考虑模块翻转和空白区域再分配的基于静电场的固定边框布图规划

引用

集成电路与嵌入式系统 2024年第1期24卷 46-57页

作者：刘端祥黄富兴李兴权朱文兴福州大学离散数学与理论计算机科学研究中心福州350108 鹏城实验室深圳518000

目前,基于解析方法的布图规划取得了很好的结果,模块翻转有实际应用场景且可以进一步优化结果,但解析方法尚无法处理模块翻转问题。因此,本文首次尝试使用统一的解析方法来解决这一问题,提出了一种新的力,即翻转力。在总体布图规划阶段... 详细信息

目前,基于解析方法的布图规划取得了很好的结果,模块翻转有实际应用场景且可以进一步优化结果,但解析方法尚无法处理模块翻转问题。因此,本文首次尝试使用统一的解析方法来解决这一问题,提出了一种新的力,即翻转力。在总体布图规划阶段,翻转力能根据线长将每个模块翻转到理想的方向。此外,基于静电场模型设计了一个新的总体布图规划流程。在该流程中,本文对超大型模块的密度计算进行了特殊处理,以减小超大型模块的排斥力,使得其他模块能更加靠近超大型模块,从而实现更加均匀的模块分布。为了更好地利用边框处缝隙中的空白区域,提出了一种边框处缝隙处理方法。最后,在布图规划算法中添加了后处理阶段以进一步优化布图结果。该后处理阶段首先基于混合整数线性规划的翻转模型对模块的翻转方向进行再次优化,然后使用本文提出的新的空白区域再分配方法。该方法减小了线性规划问题中约束条件的数量且能进行多轮次的优化,相对于以往的方法能够更有效地缩短线长。在HB+和ami49_x基准电路上,实验结果表明,本文的布图规划算法与最好的布图规划算法相比,平均半周长线长分别至少减小了13.3%和13.7%。

关键词：布图规划模块翻转总体布图规划空白区域再分配

来源：评论

学校读者我要写书评

暂无评论

无三角形图的符号边控制数下界

引用

青海师范大学学报（自然科学版） 2023年第4期39卷 53-57页

作者：潘晨佳曾庆厚福州大学离散数学与理论计算机科学研究中心福建福州350003

设G=(V,E)是一个顶点数为n的图,给定一个边权重函数f:E→{+1,-1}.如果对于任意一条边e∈E,都满足所有与边e有公共端点的边e^(*)(包括边e)的权重f(e^(*))的和大于或等于1,那么我们称这个函数f是图G的一个符号边控制函数.图G的符号边控制... 详细信息

设G=(V,E)是一个顶点数为n的图,给定一个边权重函数f:E→{+1,-1}.如果对于任意一条边e∈E,都满足所有与边e有公共端点的边e^(*)(包括边e)的权重f(e^(*))的和大于或等于1,那么我们称这个函数f是图G的一个符号边控制函数.图G的符号边控制数定义为γ′s(G)=min{Σe∈Ef(e)},其中f是G的一个符号边控制函数.本文主要研究任意无三角形图的符号边控制数的下界.

关键词：符号边控制函数符号边控制数无三角形图

来源：评论

学校读者我要写书评

暂无评论

一类奇半团的Gallai猜想研究

引用

宁夏师范学院学报 2025年第04期 24-31页

作者：谢丹刘清海洪艳梅湄洲湾职业技术学院基础教育学院福州大学离散数学与理论计算机研究中心福州大学数学与统计学院

图的路分解指一个覆盖该图所有边的边不交路的集合,设pn（G）为图G的路分解中路的个数的最小值．Gallai猜想任意n个点的简单连通图G都满足■．奇半团是由2k+1个点的完全图删去至多k-1条边得到的图,记为Godd=K2k+1-H,其中e（H）≤k-1．... 详细信息

图的路分解指一个覆盖该图所有边的边不交路的集合,设pn（G）为图G的路分解中路的个数的最小值．Gallai猜想任意n个点的简单连通图G都满足■．奇半团是由2k+1个点的完全图删去至多k-1条边得到的图,记为Godd=K2k+1-H,其中e（H）≤k-1．借助完全图的哈密顿圈分解,证明当H的每个连通分支是特殊的毛虫树时,■．这一方法有助于稠密图的Gallai猜想研究．

关键词： Gallai猜想奇半团哈密顿圈分解正交

来源：评论

学校读者我要写书评

暂无评论

超大规模集成电路布局的优化模型与算法

引用

运筹学学报 2021年第3期25卷 15-36页

作者：黄志鹏李兴权朱文兴福州大学离散数学与理论计算机科学研究中心福建福州350116 鹏城实验室广东深圳518055

布局确定集成电路单元在芯片中的具体位置,在单元互不重叠的基础上优化一些性能指标。该问题是NP困难的组合优化问题,是超大规模集成电路物理设计的核心问题之一,对集成电路的性能指标,如线网可布通性、时延、功耗、电路可靠性等有重大... 详细信息

布局确定集成电路单元在芯片中的具体位置,在单元互不重叠的基础上优化一些性能指标。该问题是NP困难的组合优化问题,是超大规模集成电路物理设计的核心问题之一,对集成电路的性能指标,如线网可布通性、时延、功耗、电路可靠性等有重大影响。在现代的集成电路设计中,布局问题通常包含数百万个集成电路单元,以及大小相异的异质性模块,和各种复杂的布局约束。目前的超大规模集成电路布局算法通常分解为总体布局、布局合法化和详细布局三个步骤。根据近年来集成电路布局算法的研究进展,综述并分析集成电路的总体布局、布局合法化和详细布局的相关优化模型和算法,并展望进一步的研究方向。

关键词：超大规模集成电路总体布局合法化优化算法

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：