Balanced Cut Approximation in Random Geometric Graphs

DOI10.1007/11940128_53zbMATH Open1135.68510OpenAlexW1502349883MaRDI QIDQ5459147FDOQ5459147

Authors: Fabrizio Grandoni, J. Díaz, Alberto Marchetti-Spaccamela 

Publication date: 24 April 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11940128_53

Recommendations

• Balanced cut approximation in random geometric graphs
• Approximating layout problems on random geometric graphs
• Automata, Languages and Programming
• Highly connected random geometric graphs
• Connectivity of sparse Bluetooth networks

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) Connectivity (05C40) Network design and communication in computer systems (68M10)

Cited In (6)

• Approximating layout problems on random geometric graphs
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• Balanced cut approximation in random geometric graphs
• Constant factor approximation for balanced cut in the PIE model
• Estimating perimeter using graph cuts
• Unbalanced graph cuts with minimum capacity

This page was built for publication: Balanced Cut Approximation in Random Geometric Graphs

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