On the bounded-hop MST problem on random Euclidean instances

DOI10.1016/j.tcs.2007.04.039zbMath1125.68138OpenAlexW2165923003WikidataQ61732592 ScholiaQ61732592MaRDI QIDQ2382669

Andrea E. F. Clementi, Angelo Monti, Massimo Lauria, Riccardo Silvestri, Miriam Di Ianni, Gianluca Rossi

Publication date: 2 October 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.039

zbMATH Keywords

randomized algorithmsApproximation algorithmsbounded height minimum spanning tree

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (3)

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks ⋮ On efficient connectivity-preserving transformations in a grid ⋮ Reducing the diameter of a unit disk graph via node addition

Cites Work

• Multicommodity flow models for spanning trees with hop constraints
• The Steiner tree problem with hop constraints
• Approximating the weight of shallow Steiner trees
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Approximating \(k\)-hop minimum-spanning trees
• Greedy Strikes Back: Improved Facility Location Algorithms
• STACS 2004
• The Solution of a Timetabling Problem
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the bounded-hop MST problem on random Euclidean instances