|Table of Contents|

Channel Allocation and Improper Edge Colorings of Bipartite Graphs(PDF)

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

Issue:
2023年03期
Page:
20-25
Research Field:
数学
Publishing date:

Info

Title:
Channel Allocation and Improper Edge Colorings of Bipartite Graphs
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)
Keywords:
channel allocation;  bipartite graphs;  improper edge colorings;  NP complete
PACS:
O157.6
DOI:
10.3969/j.issn.1001-4616.2023.03.004
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:
-
Last Update: 2023-09-15