Recognizing d-Interval Graphs and d-Track Interval Graphs

A d-interval is the union of d disjoint intervals on the real line. A d-track interval is the union of d disjoint intervals on d disjoint parallel lines called tracks, one interval on each track. As generalizations of the ubiquitous interval graphs, d-interval graphs and d-track interval graphs have wide applications, traditionally to scheduling and resource allocation, and more recently to bioinformatics. In this paper, we prove that recognizing d-track interval graphs is NP-complete for any constant d≥2. This confirms a conjecture of Gyárfás and West in 1995. Previously only the complexity of the case d=2 was known. Our proof in fact implies that several restricted variants of this graph recognition problem, i.e., recognizing balanced d-track interval graphs, unit d-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 unit d-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.     

Tree Spanners for Bipartite Graphs and Probe Interval Graphs

A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in (m log n) time.     

Scheduling with Conflicts on Bipartite and Interval Graphs

In this paper, we consider the on-line scheduling of jobs that may be competing for mutually exclusive resources. We model the conflicts between jobs with a conflict graph, so that the set of all concurrently running jobs must form an independent set in the graph. This model is natural and general enough to have applications in a variety of settings; however, we are motivated by the following two specific applications: traffic intersection control and session scheduling in high speed local area networks with spatial reuse. Our results focus on two special classes of graphs motivated by our applications: bipartite graphs and interval graphs. The cost function we use is maximum response time. In all of the upper bounds, we devise algorithms which maintain a set of invariants which bound the accumulation of jobs on cliques (in the case of bipartite graphs, edges) in the graph. The lower bounds show that the invariants maintained by the algorithms are tight to within a constant factor. For a specific graph which arises in the traffic intersection control problem, we show a simple algorithm which achieves the optimal competitive ratio.     

On the Sum Coloring Problem on Interval Graphs

In this paper we study the following NP-complete problem: given an interval graph G = (V,E) , find a node p -coloring such that the cost is minimal, where denotes a partition of V whose subsets are ordered by nonincreasing cardinality. We present an O(m χ (G) + n log n) time ε -approximate algorithm (ε < 2) to solve the problem, where n , m , and χ #(G) are the number of nodes of the interval graph, its number of cliques, and its chromatic number, respectively. The algorithm is shown to solve the problem exactly on some classes of interval graphs, namely, the proper and the containment interval graphs, and the intersection graphs of sets of ``short' intervals. The problem of determining the minimum number of colors needed to achieve the minimum over all p -colorings of G is also addressed. Received February 1, 1996; revised August 22, 1997.     

A Fully Dynamic Graph Algorithm for Recognizing Interval Graphs

We present the first dynamic graph algorithm for recognizing interval graphs. The algorithm runs in O(nlog?n) worst-case time per edge deletion or edge insertion, where n is the number of vertices in the graph. The algorithm uses a new representation of interval graphs called the train tree, which is based on the clique-separator graph representation of chordal graphs. The train tree has a number of useful properties and it can be constructed from the clique-separator graph in O(n) time.     

带权区间图的最短路算法

提出一个解带权区间图的最短路问题的O(nα(n))时间新算法，其中n是带权区间图中带权区间的个数，α(n)是单变量Ackerman函数的逆函数，它是一个增长速度比log n慢得多的函数，对于通常所见到的n，α(n)≤4．本文提出的新算法不仅在时间复杂性上比直接用Dijkstra算法解带权区间图的最短路问题有较大改进，而且算法设计思想简单，易于理解和实现．     

The Longest Path Problem has a Polynomial Solution on Interval Graphs

The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno (Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC), LNCS, vol. 3341, pp. 871–883, 2004), where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm uses a dynamic programming approach and runs in O(n ⁴) time, where n is the number of vertices of the input graph.     

Parallel Algorithms for Maximum Matching in Complements of Interval Graphs and Related Problems

Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log ³ n) time using O(n/ log ² n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs. Received November 20, 1995; revised September 3, 1998.     

Sum Coloring Interval and k -Claw Free Graphs with Application to Scheduling Dependent Jobs

We consider the sum coloring and sum multicoloring problems on several fundamental classes of graphs, including the classes of interval and k-claw free graphs. We give an algorithm that approximates sum coloring within a factor of 1.796, for any graph in which the maximum k-colorable subgraph problem is polynomially solvable. In particular, this improves on the previous best known ratio of 2 for interval graphs. We introduce a new measure of coloring, robust throughput}, that indicates how quickly the graph is colored, and show that our algorithm approximates this measure within a factor of 1.4575. In addition, we study the contiguous (or non-preemptive) sum multicoloring problem on k-claw free graphs. This models, for example, the scheduling of dependent jobs on multiple dedicated machines, where each job requires the exclusive use of at most k machines. Assuming that k is a fixed constant, we obtain the first constant factor approximation for the problem.     

迪卡尔乘积图到Cayley图中的嵌入

给出了一类图（迪卡尔乘积图）到另一类图（Ｃａｙｌｅｙ图的嵌入的一般方法,这些嵌入是这样实现的：首先把迪卡尔乘积图的每个“因子”图嵌入到主图中,然后取这些“因子”嵌入的积,进上步给出了一个定理,用来通过“因子”嵌入的性质来计算乘积嵌入的膨胀度。     

数据清理中不完整数据的清理方法

针对数据源中出现的不完整数据,提出一种有效的清理方法。     

Interval Integration

Editorial Commentary

Interval Integration     

An Internal Presentation of Regular Graphs by Prefix-Recognizable Graphs

The study of infinite graphs has potential applications in the specification and verification of infinite systems and in the transformation of such systems. Prefix-recognizable graphs and regular graphs are of particular interest in this area since their monadic second-order theories are decidable. Although the latter form a proper subclass of the former, no characterization of regular graphs within the class of prefix-recognizable ones has been known, except for a graph-theoretic one in [2]. We provide here three such new characterizations. In particular, a decidable, language-theoretic, necessary and sufficient condition for the regularity of any prefix-recognizable graph is established. Our proofs yield a construction of a deterministic hyperedge-replacement grammar for any prefix-recognizable graph that is regular. Received July 19, 1999, and in revised form December 22, 2000, and in final form March 28, 2001. Online publication July 20, 2001.     

Embedding Cartesian Products of Graphs into de Bruijn Graphs

Given a Cartesian productG=G₁× … ×G_m(m≥ 2) of nontrivial connected graphsG_iand then-dimensional baseBde Bruijn graphD=D_B(n), it is investigated whether or notGis a spanning subgraph ofD. Special attention is given to graphsG₁× … ×G_mwhich are relevant for parallel computing, namely, to Cartesian products of paths (grids) or cycles (tori). For 2-dimensional de Bruijn graphsD, we present a theorem stating that certain structural assumptions on the factorsG₁, …,G_mensure thatG₁× … ×G_mis a spanning subgraph ofD. As corollaries, we obtain results improving previous results of Heydemannet al.(J. Parallel Distrib. Comput.23 (1994), 104–111) on embedding grids and tori into de Bruijn graphs. Specifically, we obtain that (i) any gridG=G₁× … ×G_mis a spanning subgraph ofD=D_B(2) provided that |G| = |D|, and (ii) any torusG=G₁× … ×G_mis a spanning subgraph ofD=D_B(2) provided that |G| = |D| and that theG_iare cycles of even length ≥4. We show that these results have consequences for the casen> 2, too: for evenn, we apply our results to obtain embeddings of grids and toriGinto de Bruijn graphsD_B(n) with dilationn/2, where the baseBis a fixed integer ≥2, andnis big enough to ensure |G| ≤ |D_B(n)|. We also contrast our results forn= 2 with nonexistence results forn≥ 3 and briefly describe experimental results in the area of parallel image processing.     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.