Narrow Results

Inspired by a real-life application, we investigate the computationally hard problem of extending a precoloring of an interval graph to a proper coloring under some bound on the number of available colors. We are interested in quickly determining whether or not such an extension exists on instances occurring in practice in connection with campsite bookings on a campground. A naive exhaustive search does not terminate in reasonable time. We have formulated a new approach which moves the computation time within the usable range on all the data samples available to us.

Evidence is given to suggest that minimally vertex colouring an interval graph may not be in NC¹. This is done by showing that 3-colouring a linked list is NC¹-reducible to minimally colouring an interval graph. However, it is shown that an interval graph with a known interval representation and an O(1) chromatic number can be minimally coloured in NC¹.

For the CRCW PRAM model, an o(log n) time, polynomial processors algorithm is obtained for minimally colouring an interval graph with o(log n) chromatic number and a known interval representation. In particular, when the chromatic number is O((log n)^1-ε), 0<ε<1, the algorithm runs in O(log n/log log n) time. Also, an O(log n) time, O(n) cost, EREW PRAM algorithm is found for interval graphs of arbitrary chromatic numbers. The following lower bound result is also obtained: even when the left and right endpoints of the interval are separately sorted, minimally colouring an interval graph needs Ω(log n/log log n) time, on a CRCW PRAM, with a polynomial number of processors.

We develop efficient parallel maximum matching algorithms in interval graphs by exploiting special properties of interval graphs. For general interval graphs, our algorithm requires O(log²v+(n log n/v) time and O(nv²+n²) operations on the CREW PRAM, where n is the number of intervals and v≤n is a parameter. By choosing , we obtain an -time algorithm in O(n²) operations. For v=n/log n, we have an O(log²n)-time algorithm in O(n³/log²n) operations. The best previously known solution takes O(log²n) time using O(n³log²n) operations. For proper interval graphs, our algorithm runs in O(log n) time using O(n) operations if input intervals are sorted and using O(nlog n) operations otherwise on the EREW PRAM.

We present an algorithm for the All Pairs Shortest Distance problem on an interval graph on n vertices: after O(n) preprocessing time, the algorithm can deliver a response to a distance query in O(1) time. The method used here is simpler than the method of Chen et al. [4], which has the same preprocessing and query time. It is assumed that an interval model for the graph is given, and ends of intervals are already sorted by coordinate. The preprocessing algorithm can be executed in the EREW PRAM model in O(log n) time, using n/log n processors. These algorithms (sequential and parallel) may be extended to circular arc graphs, with the same time and processor bounds.

A set of vertices D is a dominating set of a graph G=(V, E) if every vertex in V−D is adjacent to at least one vertex in D. The domatic partition of G is the partition of the vertex set V into a maximum number of dominating sets. In this paper, we present efficient parallel algorithms for finding the domatic partition of Interval graphs, Block graphs and K-trees.

In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as "subroutines" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a "forbidden subgraph" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O(log n)-approximation algorithm for it.

For a fixed positive integer $k$, a $k$-hop dominating set$D$ of a graph $G=(V,E)$ is a subset of $V$ such that every vertex $x\in V$ is within $k$-steps from at least one vertex $y\in D$, i.e., $d(x,y)\le k$. A $k$-hop dominating set $D$ is said to be minimal if there does not exist any $D^{\prime }\subset D$ such that $D^{\prime }$ is a $k$-hop dominating set of G. A dominating set $D$ is said to be minimum $k$-hop dominating set, if it is minimal as well as it is $k$-hop dominating set. In this paper, we present an optimal algorithm to find a minimum $k$-hop dominating set of interval graphs with $n$ vertices which runs in $O(n)$ time.

We propose a modification of the First-Fit algorithm in which we forbid the use of the most frequently used color. We provide some lower bound of the performance ratio $\frac{{\chi }_{\mathrm{\text{FF}}wP}(G)}{\omega (G)}$ on the family of interval graphs $G$, where ${\chi }_{\mathrm{\text{FF}}wP}(G)$ denotes the number of used colors by the modified version of the First-Fit algorithm and $\omega (G)$ is the number of vertices in the largest complete subgraph in $G$. We also compare the modification with the usual First-Fit algorithm on some experimental data.