Recognizing d-Interval Graphs and d-Track Interval Graphs
Recognizing d-Interval Graphs and d-Track Interval Graphs
复制标题
DOI：
10.1007/s00453-012-9651-5
复制
发表时间：
2010-08
期刊：
影响因子：
1.1
通讯作者：
Minghui Jiang
中科院分区：
文献类型：
--
作者：
Minghui Jiang
Ad-区间是真实的直线上d个不相交区间的并集。轨道间隔是在称为轨道的不相交平行线上的不相交间隔的联合，每个轨道上有一个间隔。作为区间图的推广，d-区间图和d-轨道区间图在传统的调度和资源分配以及最近的生物信息学中有着广泛的应用。本文证明了对任意常数td ≥2，可识别的d-迹区间图是NP-完全的.这证实了Gyárfás和West在1995年的一个猜想。以前只知道cased=2的复杂度。我们的证明实际上意味着这个图识别问题的几个限制性变体，即，已知平衡轨区间图、单位轨区间图和（2，.，2）d-轨区间图都是NP-完全图。这部分回答了Gambette和Vialette最近提出的另一个问题。我们还证明了识别深度为2的2-轨区间图是NP-完全的，即使是单位的情况下。与此形成鲜明对比的是，我们提出了一个简单的线性时间算法来识别深度为2的单位区间图。我们的这些结果和其他结果部分地回答了1984年West和Shmoys提出的一个问题，以及1995年Gyárfás和West提出的一个类似问题。最后，我们给出了图的迹数和单位迹数的第一界，并将这两个数与荫度的经典概念联系起来。
Ad-intervalis the union ofddisjoint intervals on the real line. Ad-track intervalis the union ofddisjoint intervals onddisjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs,d-interval graphs andd-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizingd-track interval graphs is NP-complete for any constantd≥2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the cased=2 was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balancedd-track interval graphs, unitd-track interval graphs, and (2,…,2)d-track interval graphs, are all NP-complete. This partially answers another question recently raised by Gambette and Vialette. We also prove that recognizing depth-two 2-track interval graphs is NP-complete, even for the unit case. In sharp contrast, we present a simple linear-time algorithm for recognizing depth-two unitd-interval graphs. These and other results of ours give partial answers to a question of West and Shmoys in 1984 and a similar question of Gyárfás and West in 1995. Finally, we give the first bounds on the track number and the unit track number of a graph in terms of the number of vertices, the number of edges, and the maximum degree, and link the two numbers to the classical concepts of arboricity.