南京师大学报(自然科学版)2023，Vol.46Issue(3) ：20-25.DOI:10.3969/j.issn.1001-4616.2023.03.004

信道分配与二部图的非正常边染色

Channel Allocation and Improper Edge Colorings of Bipartite Graphs

张昊 赵燕
南京师大学报(自然科学版)2023，Vol.46Issue(3) ：20-25.DOI:10.3969/j.issn.1001-4616.2023.03.004
✕
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 维普
  • 万方数据

信道分配与二部图的非正常边染色

Channel Allocation and Improper Edge Colorings of Bipartite Graphs

张昊 1赵燕2
扫码查看

作者信息

  • 1. 南京工程学院数理学院,江苏 南京 211167
  • 2. 南京师范大学数学科学学院,江苏 南京 210023;泰州学院数理学院,江苏 泰州 225300
  • 折叠

摘要

确定二部图的边染色数和极小边染色是计算机领域的一个经典算法问题.该问题在信道分配和计算机科学的众多方面有广泛应用,并且是NP完全的.本文首先从二部图结构入手,利用非正常边染色定义,采用构造方法得到亏格为 1 和 2 时部分完全二部图的非正常边染色数,给出相应算法和复杂性分析,然后将其转化为网络中的信道数量.

关键词

信道分配/二部图/非正常边染色/NP完全

Key words

channel allocation/bipartite graphs/improper edge colorings/NP complete

引用本文复制引用

基金项目

国家自然科学基金(11901426)

江苏省高校"青蓝工程"资助项目()

出版年

2023
南京师大学报(自然科学版)
南京师范大学

南京师大学报(自然科学版)

CSTPCD北大核心
影响因子：0.427
ISSN：1001-4616
参考文献量3
段落导航相关论文