Finding All the Edge Colorings in Bipartite Graphs
Finding All the Edge Colorings in Bipartite Graphs
复制标题
查找二分图中的所有边着色
DOI：
10.1541/ieejeiss1987.114.4_444
复制
发表时间：
1994
影响因子：
--
通讯作者：
Tomomi Matsui
中科院分区：
文献类型：
--
作者：
Yasuko Yoshida;Tomomi Matsui
边着色问题用尽可能少的颜色为给定图的边分配颜色，这样相邻的两条边就不会收到相同的颜色。此问题出现在许多应用程序设置中。例如置换网络中的路由、开放车间的抢先调度、无关并行处理器的抢占调度以及班主任时间表问题。当一个给定的图是二部图时，已经给出了求边着色的强多项式时间算法。本文提出了一个求无平行边二部图的全部边染色的算法。我们的算法需要O(Km(d‘+logn))时间和O(d`m2)空间，其中n(M)表示顶点(边)数，d’表示最大度，K表示边着色数。虽然时间复杂度与边缘着色的数量成正比，但存储空间并不依赖于它。
The edge coloring problem finds an assignment of colors to the edges of a given graph using as few colors as possible, so that no two adjacent edges receive the same colors. This problem arises in many application settings. Examples are routing in a permutation network, a preemptive scheduling of an open shop, a preemptive scheduling of unrelated parallel processors, and a class-teacher timetable problem. When a given graph is bipartite, strongly polynomial time algorithms for finding an edge coloring have previously been given. In this paper, we propose an algorithm for finding all the edge colorings of bipartite graphs without parallel edges. Our algorithm requires O(Km(d' + log n)) time and O(d`m2) space, where n (m) denotes the number of vertices (edges), d' denotes the maximum degree, and K denotes the number of edge colorings. Although the time complexity is proportional to the number of edge colorings, the memory space doesn't depend on-it.