Reducing the diameter of a unit disk graph via node addition

DOI10.1016/J.IPL.2015.06.015zbMATH Open1331.68292OpenAlexW819274831MaRDI QIDQ2353655FDOQ2353655

Gianluca Rossi, Miriam Di Ianni, Luciano Gualà

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

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

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)

Cites Work

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

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)