Two Problems in Graph Theory
Two Problems in Graph Theory
复制标题
图论中的两个问题
DOI：
10.1090/dol/009/05
复制
发表时间：
1982
影响因子：
0.5
通讯作者：
R. Cole
中科院分区：
文献类型：
--
作者：
R. Cole
首先，给出了求二部图的最小边染色问题的两种方法。这些算法的运行时间分别为0（E log D + V log V log（'3）D）和0（E log D + V log V log（' 2）D），其中D是图的价。这些与Gabow和Kariv的0（min {E log（'2）V，V（' 2）log V}）时间界限相比是有利的。对于有界效价的图，第二个算法很容易修改为在0（E）时间内运行。
其次，研究了图的同构与图的刚性之间的关系。虽然在一般情况下，它是不知道，如果这些问题是等价的多项式时间图灵约简，等价的一个子类的图与阿贝尔自同构群。
Firstly, two approaches to the problem of finding a minimal edge coloring of a bipartite graph are presented. These yield algorithms with running times of 0(E log D + V log V log('3) D), and 0(E log D + V log V log('2) D), respectively, where D is the valence of the graph. These compare favourably to the 0(min {E log('2) V, V('2) log V}) time bound due to Gabow and Kariv. For graphs of bounded valence the second algorithm is easily modified to run in 0(E) time.
Secondly, the relationship between graph isomorphism and graph rigidity is studied. Although in general it is not known if these problems are equivalent under polynomial time Turing reductions, equivalence is shown for a subclass of graphs with abelian automorphism groups.