37
Views
0
CrossRef citations to date
0
Altmetric
Section A

Additive tree 2-spanners of permutation graphs

&
Pages 1490-1497 | Received 29 Nov 2005, Accepted 01 Nov 2007, Published online: 22 Jul 2009

References

  • Buckley , F. and Harary , F. 1990 . Distance in Graphs , Edited by: Buckley , F. and Harary , F. New York : Addison-Wesley .
  • Cai , L. and Corneil , D. G. 1995 . Tree spanners . SIAM J. Discrete Math. , 8 ( 3 ) : 359 – 387 .
  • Chen , H. C. , Wu , S. H. and Yang , C. B. 2003 . Efficient algorithms for finding a tree 3-spanner on permutation graphs . IEICE Trans. Inf. Syst. , E86-D ( 11 ) : 2390 – 2394 .
  • Dragan , F. F. , Yan , C. and Corneil , D. G. 2006 . Collective tree spanners and routing in AT-free related graphs . J. Graph Algorithms Appl. , 10 ( 2 ) : 97 – 122 .
  • Golumbic , M. C. 1980 . Algorithmic Graph Theory and Perfect Graphs , Edited by: Golumbic , M. C. New York : Academic Press .
  • Greenlaw , R. 1992 . A model classifying algorithms as inherently sequential with applications to graph searching . Inf. Comput. , 97 ( 2 ) : 133 – 149 .
  • JáJá , J. 1992 . Introduction to Parallel Algorithms , Edited by: JáJá , J. New York : Addison-Wesley .
  • Kratsch , D. 2003 . Additive tree spanners . SIAM J. Discrete Math. , 17 ( 2 ) : 332 – 340 .
  • Liestman , A. L. and Shermer , T. 1993 . Additive graph spanners . Networks , 23 ( 4 ) : 343 – 364 .
  • Madanlal , M. S. , Venkatesan , G. and Pandu Rangan , C. 1996 . Tree 3-spanners on interval, permutation and regular bipartite graphs . Inf. Process. Lett. , 59 ( 2 ) : 97 – 102 .
  • Peleg , D. and Ullman , J. 1989 . An optimal synchronizer for the hypercube . SIAM J. Comput. , 18 ( 4 ) : 740 – 747 .
  • Rhee , C. 1994 . Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs . Inf. Process. Lett. , 49 ( 1 ) : 45 – 50 .
  • Torre , P. and Kruskal , C. P. 1995 . Fast parallel algorithms for all-sources lexicographic search and path-algebra problems . J. Algorithms , 19 ( 1 ) : 1 – 24 .

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.