Portal de Periódicos da CAPES

A Data Structure on Interval Graphs and Its Applications

1997; World Scientific; Volume: 07; Issue: 03 Linguagem: Inglês

10.1142/s0218126697000127

1793-6454

Madhumangal Pal, G. P. Bhattacharjee,

Neural Networks and Applications

In this papar, a new data structure, interval tree (IT), is introduced for an interval graph. Some important properties of IT are studies from the algorithmic point of view. It has many advantages compared to the data structures which are commonly used to solve the problems on interval graphs. Using the properties of IT, the following problems are solved on interval graphs: (i) shortest distances between any two vertices, and (ii) the diameter of the graph.