2014/07/30 by Sambhu Charan Barman, Barman, Sambhu Charan, Sukumar Mondal +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems #cs.DM
paper · pdf · doi:10.48550/arxiv.1407.8132
16 pages
openalex publication_date 2014/07/30 · arxiv created 2014/08/11 · arxiv updated 2014/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a graph, a spanning tree is said to be a tree t-spanner of the graph if the distance between any two vertices in is at most times their distance in . The tree t-spanner has many applications in networks and distributed environments. In this paper, an algorithm is presented to find a tree -spanner on trapezoid graphs in time, where is the number of vertices of the graph.