Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes

DOI10.1016/j.ipl.2022.106265OpenAlexW4213457271MaRDI QIDQ2671810

Fernanda Couto, Luís Cunha, Leandro Santiago, Daniel Juventude

Publication date: 3 June 2022

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2022.106265

zbMATH Keywords

heuristicsgraph algorithmstree \(t\)-spanner

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Tree 3-spanners on generalized prisms of graphs

Cites Work

• Efficient graph representations
• Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs
• Hardness and efficiency on minimizing maximum distances in spanning trees
• Tree \(t\)-spanners of a graph: minimizing maximum distances efficiently
• Emergence of Scaling in Random Networks
• On pendant vertices in random graphs
• An optimal parallel algorithm to construct a tree 3-spanner on interval graphs
• Tree Spanners
• Collective dynamics of ‘small-world’ networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes