A linear time algorithm to construct a tree 4-spanner on trapezoid graphs
From MaRDI portal
Publication:3568416
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
Analysis of algorithms (68W40) Trees (05C05) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
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