An optimal parallel algorithm to construct a tree 3-spanner on interval graphs

References

• Golumbic MC 1980 Algorithmic Graph Theory and Perfect Graphs ( New York Academic Press
   Google Scholar
• Jungck , JR , Dick , O and Dick , AG . 1982 . Computer assisted sequencing, interval graphs and molecular evolution . Biosystem , 15 : 259 – 273 .
   Google Scholar
• Fabri J 1982 Automatic Storage Optimization ( MI Ann Arbor UMI Press )
   Google Scholar
• Ohtsuki , T , Mori , H , Khu , ES , Kashiwabara , T and Fujisawa , T . 1979 . One dimensional logic gate assignment and interval graph . IEEE Transactions on Circuits and Systems , 26 : 675 – 684 .
   Google Scholar
• Carlisle MC Loyd EL 1991 On the k-coloring of intervals LNCS, 497, ICCI’91 90 101
   Google Scholar
• Hashimoto A Stevens J 1971 Wire routing by optimizing channel assignment within large apertures Proceedings 8th IEEE Design Automation Workshop 155 169
   Google Scholar
• Peleg D Ullman JD 1987 An optimal synchronizer for the hypercube Proceedings of the 6th ACM Symposium on Principles of Distributed Computing Vancouver 77 85
   Google Scholar
• Awerbuch , B . 1985 . Complexity of network synchronization . Journal of the ACM , 32 : 804 – 823 .
   Google Scholar
• Peleg D Upfal E 1988 A tradeoff between space and efficiency for routing tables Proceedings of the 20th ACM Symposium on Theory of Computing Chicago 43 52
   Google Scholar
• Chew LP 1986 There is a planer graph almost as good as the complete graph Proceedings 2nd ACM Symposium on Computational Geometry ( NY Yorktown Heights ) 169 177
   Google Scholar
• Bandelt , H and Dress , A . 1986 . Reconstructing the shape of a tree from observed dissimilarity data . Advances in Applied Mathematics , 7 : 309 – 343 .
   Web of Science ®Google Scholar
• Cai , L . 1994 . NP-completeness of minimum spanner problems . Discrete Applied Mathematics , 48 : 187 – 194 .
   Google Scholar
• Cai , L and Keil , M . 1994 . Spanner in graphs of bounded degree . Network , 24 : 233 – 249 .
   Web of Science ®Google Scholar
• Madanlal , MS , Venkatesan , G and Pandu Rangan , C . 1996 . Tree 3-spanners on interval, permutation and regular bipartite graphs . Information Processing Letters , 59 : 97 – 102 .
   Google Scholar
• Venkatesan , G , Rotics , U , Madanlal , MS , Makowsky , JA and Pandu Rangan , C . 1997 . Restrictions of minimum spanner problems . Information and Computation , 136 : 143 – 164 .
   Google Scholar
• Makowsky JA Rotics U 1996 Spanner in interval and chordal graphs. Technical report, Department of Computer Science, Technion—Israel Institute of Technology
   Google Scholar
• Ramalingam , G and Pandu Rangan , C . 1988 . A unified approach to domination problem in interval graphs . Information Processing Letters , 27 : 271 – 274 .
   Web of Science ®Google Scholar
• Pal , M and Bhattacharjee , GP . 1997 . A data structure on interval graphs and its applications . Journal of Circuits Systems and Computers , 7 ( 3 ) : 165 – 175 .
   Google Scholar
• Pal , M and Bhattacharjee , GP . 1997 . An optimal parallel algorithm for all-pairs shortest paths on unweighted interval graphs . Nordic Journal of Computing , 4 : 342 – 356 .
   Google Scholar
• Pal , M and Bhattacharjee , GP . 1995 . Optimal sequential and parallel algorithms for computing the diameter and the centre of an interval graph . International Journal of Computer Mathematics , 59 : 1 – 13 .
   Web of Science ®Google Scholar
• Chen , CCY , Das , SK and Akl , SG . 1991 . A unified approach to parallel depth-first traversal of general trees . Information Processing Letters , 38 : 49 – 55 .
   Web of Science ®Google Scholar