[1]张 昊,赵 燕.信道分配与二部图的非正常边染色[J].南京师大学报(自然科学版),2023,46(03):20-25.[doi:10.3969/j.issn.1001-4616.2023.03.004]
　Zhang Hao,Zhao Yan.Channel Allocation and Improper Edge Colorings of Bipartite Graphs[J].Journal of Nanjing Normal University(Natural Science Edition),2023,46(03):20-25.[doi:10.3969/j.issn.1001-4616.2023.03.004]
点击复制

信道分配与二部图的非正常边染色()
分享到：

《南京师大学报（自然科学版）》[ISSN:1001-4616/CN:32-1239/N]

卷:
第46卷
期数:
2023年03期
页码:
20-25
栏目:
数学
出版日期:
2023-09-15

文章信息/Info

Title:
Channel Allocation and Improper Edge Colorings of Bipartite Graphs
文章编号:
1001-4616(2023)03-0020-06
作者:
张 昊1; 赵 燕2; 3
(1.南京工程学院数理学院,江苏 南京 211167)
(2.南京师范大学数学科学学院,江苏 南京 210023)
(3.泰州学院数理学院,江苏 泰州 225300)
Author(s):
Zhang Hao1; Zhao Yan2; 3
(1.School of Mathematics and Physics,Nanjing Institute of Technology,Nanjing 211167,China)
(2.School of Mathematical Science,Nanjing Normal University,Nanjing 210023,China)
(3.Department of Mathematics,Taizhou University,Taizhou 225300,China)
关键词:
信道分配; 二部图; 非正常边染色; NP完全
Keywords:
channel allocation;  bipartite graphs;  improper edge colorings;  NP complete
分类号:
O157.6
DOI:
10.3969/j.issn.1001-4616.2023.03.004
文献标志码:
A
摘要:
确定二部图的边染色数和极小边染色是计算机领域的一个经典算法问题. 该问题在信道分配和计算机科学的众多方面有广泛应用,并且是NP完全的. 本文首先从二部图结构入手,利用非正常边染色定义,采用构造方法得到亏格为1和2时部分完全二部图的非正常边染色数,给出相应算法和复杂性分析,然后将其转化为网络中的信道数量.
Abstract:
Finding the edge chromatic number and minimal edge chromatic in bipartite graphs is a well-known algorithm problem in the computer field. It has wide application in channel allocation and many aspects of computer science and it is NP complete. From the structure of bipartite graphs and the definition of improper edge colorings,this paper presents some chromatic index of bipartite graphs when the deficiency is 1 or 2 and the algorithm and complexity analysis are also given.What's more,transforms it to the numbers of channel in a network.

参考文献/References:

[1]王家恒,乐煜炜,张博文,等. 区块链无线接入网:面向未来移动通信的新架构[J]. 西安电子科技大学学报,2020,47(5):3-10.
[2]张文军,管云峰,何大治,等. 新一代融合媒体网络架构[J]. 通信学报,2019,40(8):13-21.
[3]卢小峰,朱光喜,宁国勤,等. 一种自适应跨层空间子信道分配算法——基于多用户MIMO/OFDM系统[J]. 计算机科学,2006(11):10-13.
[4]BONDY J A,MURTY U S R. Graph theory with application[M]. London:Macmillan Press Ltd,1976.
[5]COWEN L J,COWEN R H,WOODALL D R. Defective colorings of graphs in surfaces:partitions into subgraphs of bounded valency[J]. Journal of graph theory,1986,10(3):187-195.
[6]HOLYER I. The NP-completeness of edge-coloring[J]. SIAM journal on computing,1981,10:718-720.
[7]COLE R,OST K,SCHIRRA S. Edge-coloring bipartite multigraphs in O(ElogD)time[J]. Combinatorica,2001,21(1):5-12.
[8]GOTLIEB C C. The construction of class-teacher time-tables[C]//Proceedings of IFIP congress 62,North-Holland,Amsterdam,1963:73-77.
[9]CHAO H J,JING Z G,LIEW S Y. Matching algorithms for three-stage bufferless Clos network switches[J]. IEEE communications magazine,2003,41(10):46-54.
[10]陈祥恩,姚兵. K4VKn的Smarandachely邻点可区别正常边染色(英文)[J]. 数学季刊(英文版),2014,29(1):76-87.
[11]CASSELGRENA1 C J,PETROSYANB P A. Improper interval edge colorings of graphs[J]. Discrete applied mathematics,2021,305:164-178.

备注/Memo

备注/Memo:
收稿日期:2022-07-27.
基金项目:国家自然科学基金项目(11901426)、江苏省高校“青蓝工程”资助项目.
通讯作者:赵燕,博士,副教授,研究方向:图论与组合优化. E-mail:zhaoyan81.2008@163.com
更新日期/Last Update: 2023-09-15