Balanced cut approximation in random geometric graphs

DOI10.1016/J.TCS.2009.03.037MaRDI QIDQ1029344zbMATH OpenOpenAlexFDO

Authors J. Díaz, Fabrizio Grandoni, 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)

Recommendations

• Balanced Cut Approximation in Random Geometric Graphs
• Quasi-randomness of graph balanced cut properties
• Optimal Cheeger cuts and bisections of random geometric graphs
• The cut metric, random graphs, and branching processes
• Extremal cuts of sparse random graphs
• On the maximal cut in a random hypergraph
• On the max-cut of sparse random graphs
• A probabilistic result for the max-cut problem on random graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• scientific article; zbMATH DE number 1982179 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A polylogarithmic approximation of the minimum bisection
• Approximating layout problems on random geometric graphs
• Finding Separator Cuts in Planar Graphs within Twice the Optimal
• Finding good approximate vertex and edge partitions is NP-hard
• Random Geometric Graphs
• Random Plane Networks
• Sharp thresholds for monotone properties in random geometric graphs
• Unit disk graphs

Cited in

(8)

• Unbalanced graph cuts with minimum capacity
• On the unbalanced cut problem and the generalized Sherrington-Kirkpatrick model
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Balanced Cut Approximation in Random Geometric Graphs
• Constant factor approximation for balanced cut in the PIE model
• Approximating layout problems on random geometric graphs
• Estimating perimeter using graph cuts
• Optimal Cheeger cuts and bisections of random geometric graphs

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 Q1029344)