Balanced cut approximation in random geometric graphs
type: Item
instance of: scholarly article
title: Balanced cut approximation in random geometric graphs
zbMATH Open document ID: 1175.68289
author: J. Díaz
author: Fabrizio Grandoni
author: Alberto Marchetti-Spaccamela
published in: Theoretical Computer Science
publication date: 2009-07-10T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5577382
zbMATH Keywords: ad-hoc networks
zbMATH Keywords: sensor networks
zbMATH Keywords: random geometric graphs
zbMATH Keywords: balanced cut
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.03.037
OpenAlex ID: W2010254374
cites work: Q4234075
cites work: Finding good approximate vertex and edge partitions is NP-hard
cites work: Unit disk graphs
cites work: Approximating layout problems on random geometric graphs
cites work: Q4426348
cites work: A polylogarithmic approximation of the minimum bisection
cites work: Finding Separator Cuts in Planar Graphs within Twice the Optimal
cites work: Q4198056
cites work: Random Plane Networks
cites work: Sharp thresholds For monotone properties in random geometric graphs
cites work: Q4856179
cites work: Random Geometric Graphs
DOI: 10.1016/J.TCS.2009.03.037
Recommended article: Balanced Cut Approximation in Random Geometric Graphs
Recommended article: Quasi-randomness of graph balanced cut properties
Recommended article: Optimal Cheeger cuts and bisections of random geometric graphs
Recommended article: The cut metric, random graphs, and branching processes
Recommended article: Extremal cuts of sparse random graphs
Recommended article: On the maximal cut in a random hypergraph
Recommended article: On the max‐cut of sparse random graphs
Recommended article: A probabilistic result for the max-cut problem on random graphs
description: scientific article; zbMATH DE number 5577382