𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Bounded Tree-Width and LOGCFL

✍ Scribed by E. Wanke

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
902 KB
Volume
16
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

We show that (1) the recognition of tree-width bounded graphs and (2) the decidability of graph properties--which are defined by finite equivalence relations on (h)-sourced graphs-on tree-width bounded graphs belong to the complexity class LOGCFL. This is the lowest complexity class known for these problems. Our result complements the research in a series of papers by Arnborg, Bodlaender. Chandrasekharan, Courcelle, Hedetniemi, Lagergren, Proskurowski. Reed, Robertson, Seymour, Seese, and many others. "(1) 1994 Academic Press, Inc.

πŸ“œ SIMILAR VOLUMES

Partitioning Graphs of Bounded Tree-Widt
Partitioning Graphs of Bounded Tree-Width
✍ Guoli Ding; Bogdan Oporowski; Daniel P. Sanders; Dirk Vertigan πŸ“‚ Article πŸ“… 1998 πŸ› Springer-Verlag 🌐 English βš– 199 KB
Efficient Parallel Algorithms for Graphs
Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
✍ Jens Lagergren πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 236 KB

We present an efficient parallel algorithm for the tree-decomposition problem Ε½ 3 . Ε½. for fixed width w. The algorithm runs in time O O log n and uses O O n processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decom-Ε½ 2 . position algorithm is O O n log n . The tree-decomposi

Optimal Parametric Search on Graphs of B
Optimal Parametric Search on Graphs of Bounded Tree-Width
✍ David FernΓ‘ndez-Baca; Giora Slutzki πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 339 KB

We give linear-time algorithms for a class of parametric search problems on weighted graphs of bounded tree-width. We also discuss the implications of our results to approximate parametric search on planar graphs.

Ka,k Minors in Graphs of Bounded Tree-Wi
Ka,k Minors in Graphs of Bounded Tree-Width
✍ Thomas BΓΆhme; John Maharry; Bojan Mohar πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 175 KB

It is shown that for any positive integers k and w there exists a constant N ¼ N ðk; wÞ such that every 7-connected graph of tree-width less than w and of order at least N contains K 3;k as a minor. Similar result is proved for K a;k minors where a is an arbitrary fixed integer and the required conn

Tree-width, path-width, and cutwidth
Tree-width, path-width, and cutwidth
✍ Ephraim Korach; Nir Solel πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 387 KB