An optimal parallel algorithm to construct a tree 3-spanner on interval graphs

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

zbMATH Keywords

parallel algorithmsinterval graph\(t\)-spannerdesign and analysis of algorithmstree \(t\)-spanner

Mathematics Subject Classification ID

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