40
Views
3
CrossRef citations to date
0
Altmetric
Section A

A linear time algorithm to construct a tree 4-spanner on trapezoid graphs

, &
Pages 743-755 | Published online: 16 Sep 2008

References

  • Awerbuch , B. 1985 . Complexity of network synchronization . J. ACM , 32 : 804 – 823 .
  • Bandelt , H. and Dress , A. 1986 . Reconstructing the shape of the tree from observed dissimilarity data . Adv. Appl. Math , 7 : 309 – 343 .
  • Cai , L. 1994 . NP-completeness of minimum spanner problems . Discrete Appl. Math , 48 : 187 – 194 .
  • Cai , L. and Keil , M. 1994 . Spanner in graphs of bounded degree . Network , 24 : 233 – 249 .
  • Chen , C. C.Y. and Das , S. K. 1992 . Breadth-first traversal of trees and integer sorting in parallel . Info. Process. Lett , 41 : 39 – 49 .
  • Chew , L. P. There is a planer graph almost as good as the complete graph . Proceedings 2th ACM Symposium on Computational Geometry . Yorktown Heights, NY. pp. 169 – 177 .
  • Corneil , D. G. and Kamula , P. A. Extension of permutation and interval graphs . Proceedings 18th Southeast Conference on Combinatorics, Graph Theory and Computing . pp. 267 – 276 .
  • Dagan , I. , Golumbic , M. C. and Pinter , R. Y. 1988 . Trapezoid graphs and their coloring . Discrete Appl. Math , 21 : 35 – 46 .
  • Deo , N. 1990 . Graph Theory with Applications to Engineering and Computer Science , New Delhi : Prentice Hall of India Private Limited .
  • Golumbic , M. C. 1980 . Algorithmic Graph Theory and Perfect Graphs , New York : Academic Press .
  • Liang , Y. D. 1994 . Domination in trapezoid graphs . Info. Processing Lett , 52 : 309 – 315 .
  • Ma , T. and Spinrad , J. P. An O(n2) algorithm for 2-chain problem on certain classes of perfect graphs . Proceedings 2nd ACM-SIAM Symposium on Discrete Algorithms .
  • Madanlal , M. S. , Venkatesan , G. and Pandu Rangan , C. 1996 . Tree 3-spanners on interval, permutation and regular bipartite graphs . Info. Processing Lett , 59 : 97 – 102 .
  • Makowsky , J. A. and Rotics , U. 1996 . Spanner in interval and chordal graphs , Department of Computer Science, Technion-Israel Institude of Technology . Technical report
  • Mondal , S. , Pal , M. and Pal , T. K. 2002 . An optimal algorithm for solving all-pairs shortest paths on trapezoid graphs . Int. J. Comput. Eng. Sci , 3 ( 2 ) : 103 – 116 .
  • Peleg , D. and Ullman , J. D. 1989 . An optimal synchronizer for the hypercube . SIAM J. Comput , 18 : 740 – 747 .
  • Peleg , D. and Upfal , E. A tradeoff between space and efficiency for routing tables . Proceedings of the 20th ACM Symposium on Theory of Computing . Chicago. pp. 43 – 52 .
  • Saha , A. , Pal , M. and Pal , T. K. 2005 . An optimal parallel algorithm to construct a tree 3-spanner on interval graphs . Int. J. Comput. Math , 3 : 259 – 274 .
  • Tarjan , R. E. 1972 . Depth first search and linear graph algorithm . SIAM J. Comput , 2 : 146 – 160 .
  • Venkatesan , G. , Rotics , U. , Madanlal , M. S. , Makowsky , J. A. and Pandu Rangan , C. 1997 . Restrictions of minimum spanner problems . Info. Comput , 136 : 143 – 164 .

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.