Balanced cut approximation in random geometric graphs

DOI10.1016/j.tcs.2009.03.037zbMath1175.68289OpenAlexW2010254374MaRDI QIDQ1029344

Fabrizio Grandoni, Josep Diaz, Alberto Marchetti-Spaccamela

Publication date: 10 July 2009

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

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

zbMATH Keywords

approximation algorithmssensor networksrandom geometric graphsad-hoc networksbalanced cut

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (1)

Faster Pseudopolynomial Time Algorithms for Subset Sum

Cites Work

• Unit disk graphs
• Finding good approximate vertex and edge partitions is NP-hard
• Approximating Layout Problems on Random Geometric Graphs
• A Polylogarithmic Approximation of the Minimum Bisection
• Sharp thresholds For monotone properties in random geometric graphs
• Random Plane Networks
• Finding Separator Cuts in Planar Graphs within Twice the Optimal
• Random Geometric Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Balanced cut approximation in random geometric graphs