✦ LIBER ✦

Approximating Layout Problems on Random Geometric Graphs

✍ Scribed by Josep Dı́az; Mathew D. Penrose; Jordi Petit; Marı́a Serna

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 308 KB
Volume: 39
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1149

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper, we study the approximability of several layout problems on a family of random geometric graphs. Vertices of random geometric graphs are randomly distributed on the unit square and are connected by edges whenever they are closer than some given parameter. The layout problems that we consider are bandwidth, minimum linear arrangement, minimum cut width, minimum sum cut, vertex separation, and edge bisection. We first prove that some of these problems remain NP-complete even for geometric graphs. Afterwards, we compute lower bounds that hold, almost surely, for random geometric graphs. Then, we present two heuristics that, almost surely, turn out to be constant approximation algorithms for our layout problems on random geometric graphs. In fact, for the bandwidth and vertex

📜 SIMILAR VOLUMES

On k-connectivity for a geometric random

On k-connectivity for a geometric random graph

✍ Mathew D. Penrose 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 255 KB 👁 1 views

For n points uniformly randomly distributed on the unit cube in d dimensions, ## Ž . with dG 2, let respectively, denote the minimum r at which the graph, obtained by n n adding an edge between each pair of points distant at most r apart, is k-connected Ž . w x respectively, has minimum degree k

NC-Approximation Schemes for NP- and PSP

NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

✍ Harry B Hunt III; Madhav V Marathe; Venkatesh Radhakrishnan; S.S Ravi; Daniel J 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 303 KB

We present NC-approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the same time versus performance trade-off as the best known approximation schemes for planar gr

On the equivalence of optimality criteri

On the equivalence of optimality criterion and sequential approximate optimization methods in the classical topology layout problem

✍ Albert A. Groenwold; L. F. P. Etman 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 411 KB