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

DOI10.1080/00207160412331286851MaRDI QIDQ4653706zbMATH OpenOpenAlexFDO

Authors Anita Saha, Madhumangal Pal, Tapan K. 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

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

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Optimal tree 3-spanners in directed path graphs
• Tree Spanners
• scientific article; zbMATH DE number 1281573
• Tree spanners for bipartite graphs and probe interval graphs.

Cites work

• A unified approach to domination problems on interval graphs
• A unified approach to parallel depth-first traversals of general trees
• Complexity of network synchronization
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• NP-completeness of minimum spanner problems
• One-dimensional logic gate assignment and interval graphs
• Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
• Reconstructing the shape of a tree from observed dissimilarity data
• Restrictions of minimum spanner problems
• Spanners in graphs of bounded degree
• Tree 3-spanners on interval, permutation and regular bipartite graphs

Cited in

(8)

• Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes
• A linear time algorithm to compute square of interval graphs and their colouring
• A linear time algorithm to construct a tree 4-spanner on trapezoid graphs
• An optimal algorithm to find minimum k-hop dominating set of interval graphs
• scientific article; zbMATH DE number 2092300 (Why is no real title available?)
• L(2,1)-labeling of interval graphs
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• The interval-merging problem

This page was built for publication: An optimal parallel algorithm to construct a tree 3-spanner on interval graphs

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