C Pandu Rangan

Department of Computer Science and Engineering

Computer Programming - Algorithms

DOMINATION PROBLEMS

INTERVAL GRAPHS

Linear-time algorithms

Mathematical techniques

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

A unified approach to domination problems on interval graphs

Information Processing Letters

A minimum clique-transversal set MCT(G) of a graph G=(V,E) is a set S⊆V of minimum cardinality that meets all maximal cliques in G. A maximum clique-independent set MCI(G) of G is a set of maximum number of pairwise vertex-disjoint maximal cliques. We prove that the problem of finding an MCT(G) and an MCI(G) is NP-hard for cocomparability, planar, line and total graphs. As an interesting corollary we obtain that the problem of finding a minimum number of elements of a poset to meet all maximal antichains of the poset remains NP-hard even if the poset has height two, thereby generalizing a result of Duffas et al. (J. Combin. Theory Ser. A 58 (1991) 158-164). We present a polynomial algorithm for the above problems on Helly circular-arc graphs which is the first such algorithm for a class of graphs that is not clique-perfect. We also present polynomial algorithms for the weighted version of the clique-transversal problem on strongly chordal graphs, chordal graphs of bounded clique size, and cographs. The algorithms presented run in linear time for strongly chordal graphs and cographs. These mark the first attempts at the weighted version of the problem. © 2000 Elsevier Science B.V.

Discrete Applied Mathematics

Algorithmic aspects of clique-transversal and clique-independent sets

The tree 3-spanner problem consists of finding a tree 3-spanner of a given graph G(V, E). We study the tree 3-spanner problem for some special classes of graphs namely interval graphs, permutation graphs and regular bipartite graphs.

Tree 3-spanners on interval, permutation and regular bipartite graphs

We present an O(n2) time‐optimal algorithm for solving the unweighted all‐pair shortest path problem on interval graphs, an important subclass of perfect graphs. An interesting structure called the neighborhood tree is studied and used in the algorithm. This tree is formed by identifying the successive neighborhoods of the vertex labeled last in the graph according to the IG‐ordering. Copyright © 1992 Wiley Periodicals, Inc., A Wiley Company

Networks

An optimal algorithm to solve the all‐pair shortest path problem on interval graphs

Given an integer i and an undirected graph G, the generalized i-vertex cover problem is to find a minimum set of vertices such that all cliques in G of size i contain at least one vertex from this set. This problem is known to be NP-complete for chordal graphs when i is part of the input. We present a greedy linear time algorithm for this problem in the case of interval graphs. © 1992.

Fulltext

Generalized vertex covering in interval graphs

Let G = (V, E) be an interval graph, with |V| = n, and |E| = m. An O(n2 log n) algorithm was proposed in Kratsch (Inform Comput. 74, 140-158 (1987)) to find the bandwidth of G. We show that this algorithm is wrong, and provide a corrected version of the same. Also, it was observed in [4] that the bandwidth of a proper interval graph can be computed in O(n log n + m) time. We show how this idea can be modified slightly to yield an O(n = m) algorithm. © 1991.

Journal	Information Processing Letters
ISSN	00200190
Open Access	No