𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximating the Bandwidth for Asteroidal Triple-Free Graphs

✍ Scribed by Ton Kloks; Dieter Kratsch; Haiko Müller

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
110 KB
Volume
32
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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. For the special cases of Ž 2 . permutation graphs and trapezoid graphs we obtain O n log n algorithms with Ž . worst-case performance ratio 2. For cocomparability graphs we obtain an O n q m algorithm with worst-case performance ratio 3.

📜 SIMILAR VOLUMES

Improved Bandwidth Approximation for Tre
Improved Bandwidth Approximation for Trees and Chordal Graphs
✍ Anupam Gupta 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 110 KB

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 approx

An approximate version of Hadwiger's con
An approximate version of Hadwiger's conjecture for claw-free graphs
✍ Maria Chudnovsky; Alexandra Ovetsky Fradkin 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB

## Abstract Hadwiger's conjecture states that every graph with chromatic number χ has a clique minor of size χ. In this paper we prove a weakened version of this conjecture for the class of claw‐free graphs (graphs that do not have a vertex with three pairwise nonadjacent neighbors). Our main resul

Efficient Approximation Schemes for Maxi
Efficient Approximation Schemes for Maximization Problems onK3, 3-free orK5-free Graphs
✍ Zhi-Zhong Chen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 263 KB

We show that for any integer k G 2 and any n-vertex graph G without a K 3, 3 Ž . or K minor, one can compute k induced subgraphs of G with treewidth no more 5 Ž . Ž. Ž Ž 2 .. than 3k y 4 respectively, 6 k y 7 in O kn respectively, O kn q n time such that each vertex of G appears in exactly k y 1 of

A degree condition for the existence of
A degree condition for the existence of regular factors inK1,n-free graphs
✍ Ota, Katsuhiro; Tokuda, Taro 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 260 KB 👁 2 views

A graph is called K1,.-free if it contains no K l , n as an induced subgraph. Let n ( r 3), r be integers (if r is odd, r 2 n -1). We prove that every Kl,,-free connected graph G with rlV(G)I even has an r-factor if its minimum degree is at least This degree condition is sharp.

Application of the frozen atom approxima
Application of the frozen atom approximation to the GB/SA continuum model for solvation free energy
✍ Olgun Guvench; Jörg Weiser; Peter Shenkin; István Kolossváry; W. Clark Still 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract The generalized Born/surface area (GB/SA) continuum model for solvation free energy is a fast and accurate alternative to using discrete water molecules in molecular simulations of solvated systems. However, computational studies of large solvated molecular systems such as enzyme–ligand