✦ LIBER ✦

Improved Bandwidth Approximation for Trees and Chordal Graphs

✍ Scribed by Anupam Gupta

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 110 KB
Volume: 40
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1118

No coin nor oath required. For personal study only.

✦ Synopsis

A linear arrangement of an n-vertex graph G = V E is a one-one mapping f of the vertex set V onto the set n = 0 1 n -1 . The bandwidth of this linear arrangement is the maximum difference between the images of the endpoints of any edge in E G . When the input graph G is a tree, the best known approximation algorithms for the minimum bandwidth linear arrangement (which are based on the principle of volume respecting embeddings) output a linear arrangement which has bandwidth within O log 3 n of the optimal bandwidth. In this paper, we present a simple randomized O log 2 5 n -approximation algorithm for bandwidth minimization on trees. We also show that a close variant of this algorithm gives a similar performance guarantee for chordal graphs.

📜 SIMILAR VOLUMES

Distance Approximating Trees for Chordal

Distance Approximating Trees for Chordal and Dually Chordal Graphs

✍ Andreas Brandstädt; Victor Chepoi; Feodor Dragan 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 165 KB

In this paper we show that, for each chordal graph G, there is a tree T such that T is a spanning tree of the square G 2 of G and, for every two vertices, the distance between them in T is not larger than the distance in G plus 2. Moreover, we prove that, if G is a strongly chordal graph or even a d

Strong clique trees, neighborhood trees,

Strong clique trees, neighborhood trees, and strongly chordal graphs

✍ McKee, Terry A. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 137 KB 👁 1 views

Maximal complete subgraphs and clique trees are basic to both the theory and applications of chordal graphs. A simple notion of strong clique tree extends this structure to strongly chordal graphs. Replacing maximal complete subgraphs with open or closed vertex neighborhoods discloses new relationsh

Approximating the Bandwidth for Asteroid

Approximating the Bandwidth for Asteroidal Triple-Free Graphs

✍ Ton Kloks; Dieter Kratsch; Haiko Müller 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 110 KB

We show that there is an O nm algorithm to approximate the bandwidth of an AT-free graph with worst case performance ratio 2. Alternatively, at the cost of the Ž . approximation factor, we can also obtain an O m q n log n algorithm to approximate the bandwidth of an AT-free graph within a factor 4.

Improved Approximation Algorithms for Tr

Improved Approximation Algorithms for Tree Alignment

✍ Lusheng Wang; Dan Gusfield 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 251 KB

Multiple sequence alignment is a task at the heart of much of current computaw x tional biology 4 . Several different objective functions have been proposed to formalize the task of multiple sequence alignment, but efficient algorithms are lacking in each case. Thus multiple sequence alignment is on

The degree-preserving spanning tree prob

The degree-preserving spanning tree problem in strongly chordal and directed path graphs

✍ Ching-Chi Lin; Gerard J. Chang; Gen-Huey Chen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract Suppose __G__ is a connected graph and __T__ a spanning tree of __G__. A vertex __v__ ε __V__(__G__) is said to be a degree‐preserving vertex if its degree in __T__ is the same as its degree in __G__. The degree‐preserving spanning tree problem is to find a spanning tree __T__ of a conn

An extremal bandwidth problem for bipart

An extremal bandwidth problem for bipartite graphs

✍ Robert C. Brigham; Julie R. Carrington; Ronald D. Dutton; Joseph Fiedler; Richar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 2 views