Recognizing interval bigraphs by forbidden patterns
Recognizing interval bigraphs by forbidden patterns
复制标题
通过禁止模式识别区间二联图
DOI：
10.1002/jgt.22792
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Rafiey, Arash
中科院分区：
文献类型：
--
作者：
Rafiey, Arash
设是一个有顶点和边的连通二部图。给出了判定区间偶图的一个时间算法。最著名的算法具有时间复杂性，它是由Muller在1997年开发的。我们的方法是基于Hell和Huang在2003年提出的区间偶图的序特征。我们将寻找所需排序的问题转化为选择一个对有向图的强分支而不产生冲突。我们利用对有向图的结构以及基于对有向图的特殊分量的双图分解。通过这种方式，我们明确了困难的情况是什么，并通过隔离这些情况来提高效率。
Letbe a connected bipartite graph withvertices andedges. We give antime algorithm to decide whetheris an interval bigraph. The best known algorithm has time complexityand it was developed by Muller in 1997. Our approach is based on an ordering characterization of interval bigraphs introduced by Hell and Huang in 2003. We transform the problem of finding the desired ordering to choosing strong components of a pair‐digraph without creating conflicts. We make use of the structure of the pair‐digraph as well as decomposition of bigraphbased on the special components of the pair‐digraph. This way we make explicit what the difficult cases are and gain efficiency by isolating such situations.
登录
查看更多内容
禁止的有序子图
影响因子：
6.1
作者：
P. Damaschke
通讯作者：
P. Damaschke
DOI：
10.1007/978-3-642-33090-2_51
发表时间：
2012
期刊：
J. Comb. Theory B
影响因子：
--
作者：
P. Hell;M. Mastrolilli;M. M. Nevisi;A. Rafiey
通讯作者：
A. Rafiey
一种识别区间图的增量线性时间算法
DOI：
10.1137/0218005
发表时间：
1989
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Norbert Korte;R. Möhring
通讯作者：
R. Möhring
识别多项式时间内的区间有向图和区间有向图
DOI：
10.1016/s0166-218x(97)00027-9
发表时间：
1997
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
H. Müller
通讯作者：
H. Müller
影响因子：
0.9
作者：
P. Hell;Jing Huang
通讯作者：
Jing Huang