An optimal parallel algorithm to construct a tree 3-spanner on interval graphs
From MaRDI portal
Publication:4653706
DOI10.1080/00207160412331286851zbMath1079.68111OpenAlexW2149835059MaRDI QIDQ4653706
Anita Saha, Madhumangal Pal, Tapan Kumar Pal
Publication date: 7 March 2005
Published in: International Journal of Computer Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/00207160412331286851
Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (6)
A linear time algorithm to compute square of interval graphs and their colouring ⋮ The interval-merging problem ⋮ Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ \(L(2,1)\)-labeling of interval graphs ⋮ A linear time algorithm to construct a tree 4-spanner on trapezoid graphs
Cites Work
- Unnamed Item
- Reconstructing the shape of a tree from observed dissimilarity data
- Tree 3-spanners on interval, permutation and regular bipartite graphs
- A unified approach to domination problems on interval graphs
- A unified approach to parallel depth-first traversals of general trees
- NP-completeness of minimum spanner problems
- Restrictions of minimum spanner problems
- One-dimensional logic gate assignment and interval graphs
- Complexity of network synchronization
- Spanners in graphs of bounded degree
- Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
This page was built for publication: An optimal parallel algorithm to construct a tree 3-spanner on interval graphs