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

DOI10.1080/00207160802037880zbMath1209.05236arXiv1407.8132OpenAlexW2050202009MaRDI QIDQ3568416

Sukumar Mondal, Sambhu Charan Barman, 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 algorithmsdesign of algorithmsshortest pathstrapezoid graphstree \(t\)-spanner

Mathematics Subject Classification ID

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

Related Items (1)

Computation of inverse 1-center location problem on the weighted trapezoid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing the shape of a tree from observed dissimilarity data
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Trapezoid graphs and their coloring
• Breadth-first traversal of trees and integer sorting in parallel
• NP-completeness of minimum spanner problems
• Dominations in trapezoid graphs
• Restrictions of minimum spanner problems
• Complexity of network synchronization
• Spanners in graphs of bounded degree
• An optimal parallel algorithm to construct a tree 3-spanner on interval graphs
• A trade-off between space and efficiency for routing tables
• An Optimal Synchronizer for the Hypercube
• Depth-First Search and Linear Graph Algorithms

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