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

DOI10.1080/00207160802037880MaRDI QIDQ3568416zbMATH OpenOpenAlexFDO

Authors Sambhu Charan Barman, Sukumar Mondal, Madhumangal Pal

Publication date 11 June 2010

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.8132

zbMATH Keywords

analysis of algorithmsshortest pathsdesign of algorithmstrapezoid graphstree \(t\)-spanner

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Paths and cycles (05C38)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 434687
• Tree Spanners
• Isomorphic tree spanner problems
• Optimal tree 3-spanners in directed path graphs
• A simple optimal parallel algorithm for constructing a spanning tree of a trapezoid graph

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• scientific article; zbMATH DE number 3446921 (Why is no real title available?)
• A trade-off between space and efficiency for routing tables
• An Optimal Synchronizer for the Hypercube
• An optimal parallel algorithm to construct a tree 3-spanner on interval graphs
• Breadth-first traversal of trees and integer sorting in parallel
• Complexity of network synchronization
• Depth-First Search and Linear Graph Algorithms
• Dominations in trapezoid graphs
• NP-completeness of minimum spanner problems
• Reconstructing the shape of a tree from observed dissimilarity data
• Restrictions of minimum spanner problems
• Spanners in graphs of bounded degree
• Trapezoid graphs and their coloring
• Tree 3-spanners on interval, permutation and regular bipartite graphs

Cited in

(3)

• Computation of inverse 1-center location problem on the weighted trapezoid graphs
• A linear time algorithm for finding depth-first spanning trees on trapezoid graphs
• scientific article; zbMATH DE number 1117869 (Why is no real title available?)

This page was built for publication: A linear time algorithm to construct a tree 4-spanner on trapezoid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3568416)