Balanced Cut Approximation in Random Geometric Graphs

DOI10.1007/11940128_53MaRDI QIDQ5459147zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(6)

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

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)