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

ad-hoc networksapproximation algorithmsbalanced cutrandom geometric graphssensor networks

Mathematics Subject Classification ID

Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

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)

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

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)