-
题名四正则图的交叉数
被引量:3
- 1
-
-
作者
杨元生
王丹
陆维明
-
机构
大连理工大学计算机科学与工程系
中国科学院
-
出处
《软件学报》
EI
CSCD
北大核心
2002年第12期2259-2266,共8页
-
基金
国家自然科学基金资助项目(60073013:60143002)
中国科学院数学与系统科学研究院基金资助
-
文摘
利用计算机对图的交叉数进行研究,给出了利用分支界限法计算图的交叉数的算法CCN(calculatecrossing number),并利用该算法计算出n≤12的所有四正则图的交叉数以及n≤16的随机四正则图的交叉数.同时计算出n≤12的所有四正则图的平均交叉数Aac(n)和n≤16的随机四正则图的平均交叉数Arc(n),根据计算结果提出四正则图的平均交叉数为O(n2)的猜想.
-
关键词
四正则图
交叉数
同构
平面图
分支界限法
算法
计算机
-
Keywords
crossing number
regular graph
isomorphic
plane graph
branch and bound method
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名四正则图的自动生成及纵横嵌入的线性算法
被引量:1
- 2
-
-
作者
王方石
须德
-
机构
北方交通大学计算机与信息技术学院
-
出处
《北方交通大学学报》
CSCD
北大核心
2001年第2期29-32,共4页
-
基金
国家自然科学基金资助项目!( 69973 0 0 1)
-
文摘
刘彦佩教授论述的纵横嵌入术已为超大规模集成电路 (VLSI)的平面设计提供了较完备的理论体系 ,本文以此为依据建立的算法能自动生成任意点数的四正则图例 ,并对其进行双极定向和双极标数 ,进而画出其纵横嵌入图 .在对四正则图进行双极定向时 ,根据吸收规则的原理 ,设计了一种在计算机上易于实现的算法 ,该算法已成功地绘制了含有几个点及至近千个点的四正则图的纵横嵌入图 .
-
关键词
四正则图
双极定向
双极标数
纵横嵌入
线性算法
VLSI
集成电路
-
Keywords
four regular graph
bipolar orientation
bipolar numbering
rectilinear embedding
linear algorithm
-
分类号
TN47
[电子电信—微电子学与固体电子学]
O157.6
[理学—基础数学]
-
-
题名极大平面图的导出四正则图的三着色
- 3
-
-
作者
杨宁
-
机构
中央民族大学数学与计算机科学学院
-
出处
《中央民族大学学报(自然科学版)》
2005年第4期305-310,共6页
-
文摘
本文给出了极大平面图的导出四正则图的两种构造方式、等价性及性质,证明了导出四正则图的三着色与原极大平面图四着色的一一对应关系,并且找出了导出四正则图的三种颜色与原极大平面图四着色的三组对偶二色子图之间的关系.
-
关键词
导出四正则图
对偶二色子图
正常三着色
极大平面图
对偶图
-
Keywords
inducing four regular graph
dual bi-chromatic subgraph
normal S-coloring
maximalplanar graph
dual graph
-
分类号
O157.6
[理学—基础数学]
-
-
题名四正则图的分离问题是NP-完备的(英文)
- 4
-
-
作者
刁科凤
赵平
周惠山
-
机构
临沂师专数学系
临沂市农业银行
乔治亚洲立大学数学与计算机科学系
-
出处
《数学研究》
CSCD
1999年第2期137-145,共9页
-
文摘
本 文证明了 四正则图 的最小平 分问题是 N P完备的 ,因而可得 到四正 则图的最 小 α分离问 题也是 N P完备
-
关键词
四正则图
分离问题
NP-完备性
顶点连通度
-
Keywords
Graph separation of 4 Regular Graphs
-
分类号
O157.5
[理学—基础数学]
-