Balanced cut approximation in random geometric graphs

DOI10.1016/J.TCS.2009.03.037zbMATH Open1175.68289OpenAlexW2010254374MaRDI QIDQ1029344FDOQ1029344

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

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

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)

Cites Work

• Random Geometric Graphs
• Title not available (Why is that?)
• Unit disk graphs
• Finding good approximate vertex and edge partitions is NP-hard
• Sharp thresholds for monotone properties in random geometric graphs
• Random Plane Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating layout problems on random geometric graphs
• A polylogarithmic approximation of the minimum bisection
• Title not available (Why is that?)
• Finding Separator Cuts in Planar Graphs within Twice the Optimal

Cited In (8)

• Faster Pseudopolynomial Time Algorithms for Subset Sum
• 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
• 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)