Reducing the diameter of a unit disk graph via node addition

DOI10.1016/J.IPL.2015.06.015MaRDI QIDQ2353655zbMATH OpenOpenAlexFDO

Authors Miriam Di Ianni, Luciano Gualà, Gianluca Rossi

Publication date 15 July 2015

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

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

zbMATH Keywords

approximation algorithmsgraph algorithmsgraph design optimization problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Sparse hop spanners for unit disk graphs
• Plane hop spanners for unit disk graphs: simpler and better
• Graph-Theoretic Concepts in Computer Science
• A PTAS for weak minimum routing cost connected dominating set of unit disk graph
• A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs

Cites work

• scientific article; zbMATH DE number 4137792 (Why is no real title available?)
• A fast algorithm for Steiner trees
• Balancing minimum spanning trees and shortest-path trees
• Decreasing the diameter of bounded degree graphs
• Decreasing the diameter of cycles
• Diameter bounds for altered graphs
• Diameter increase caused by edge deletion
• How to decrease the diameter of triangle-free graphs
• Improved approximability and non-approximability results for graph diameter decreasing problems
• On the bounded-hop MST problem on random Euclidean instances
• Reducibility among combinatorial problems
• The Complexity of Computing Steiner Minimal Trees
• The Steiner tree problem with hop constraints
• The complexity of designing a network with minimum diameter
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints

This page was built for publication: Reducing the diameter of a unit disk graph via node addition

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