期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

关于单位区间图的二维带宽问题

Two-dimensional bandwidth problem for unit-interval graph
下载PDF
导出
摘要 二维带宽问题是将图G的顶点嵌入平面格子图,使其最长的连线尽可能短.通过引进矩形链这一概念,给出单位区间图的二维带宽精确值. The two-dimensional bandwidth problem is to find an embedding of graph G in a grid graph in the plane so that the longest edges are as short as possible. The exact value of two-dimensional bandwidth for unitinterval graph is produced.
作者 吕红杰 申家峰 戴明清
机构地区 郑州轻工业学院信息与计算科学系 郑州航空工业管理学院基础部 华北水利水电学院数学系
出处 《郑州轻工业学院学报（自然科学版）》 CAS 2006年第1期96-99,共4页 Journal of Zhengzhou University of Light Industry:Natural Science
关键词 二维带宽 单位区间图 图的嵌入 two-dimensional bandwidth unit-interval graph graph embedding
分类号 O157.5 [理学—基础数学]
  • 相关文献

参考文献10

  • 1Lengauer T. Upper and lower bounds on the complexity of the rain-cut linear arrangement problem on trees[ J]. SIAM J Alg Discrete Methods, 1982, (3) : 99- 113.
  • 2Chung F R K. Labelings of Graphs [ M J. London : Academic Press Inc, 1988.151-168.
  • 3Lai YungLing, Kenneth Williams. A survery of solved problems and applications on bandwidth, edgesum, and profile of graphs[J] .J Graph Theory, 1999, (31) :75-94.
  • 4Bhatt S N, Leighton F T. A framework for solving VLSI graph layout problems[ J]. J Computer and System Science, 1984,28(2) :300-343.
  • 5Lin Yixun. On density lower bounds of two dimensional bandwidth[J]. J Mathematical Research and Exposition, 1996,(3) :343-349.
  • 6郝建修.[D].郑州:郑州大学数学系资料室,2001.
  • 7Golumbic M C. Algorithmic Graph Theory and Perfect Graphs[ M ]. New York : Academic Press, 1980.
  • 8原晋江,康丽英.单位区间图的一种刻划及其应用[J].石家庄铁道学院学报,1994,7(2):50-54. 被引量：4
  • 9Kaplan H, Shamir R. Pathwidth, bandwidth and completion problem to proper interval graphs with small cliques[ J]. SIAM J Comput, 1996,25(3) :540-561.
  • 10Bondy J A, Murty U S R. Graph Theory with Application[ M]. New York : Macamillan Press, 1976.

共引文献4

郑州轻工业学院学报（自然科学版）
2006年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部