✦ LIBER ✦

Efficient Parallel Algorithms for Graphs of Bounded Tree-Width

✍ Scribed by Jens Lagergren

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 236 KB
Volume: 20
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0002

No coin nor oath required. For personal study only.

✦ Synopsis

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-decomposition algorithm enables us to construct efficient parallel algorithms for a broad class of problems, when restricted to graphs of tree-width at most w. Many of these problems are NP-complete for general graphs.

📜 SIMILAR VOLUMES

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

An Efficient Parallel Algorithm for Maxi

An Efficient Parallel Algorithm for Maximum Matching for Some Classes of Graphs

✍ I. Parfenoff 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 403 KB

The P 4 -tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few induced P 4 (cographs, P 4 -sparse graphs, P 4 -lite graphs). Here, we propose an extension of R. Lin and S. Olariu's work (1994. J. Parallel Distributed Computing 22, 26 36.) on cographs, usi

Polynomial-time algorithms for solving a

Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs

✍ Siqian Shen; J. Cole Smith 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 367 KB 👁 1 views

Efficient Parallel Algorithms for Optima

Efficient Parallel Algorithms for Optimally Locating a Path and a Tree of a Specified Length in a Weighted Tree Network

✍ Biing-Feng Wang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 128 KB

In this paper, we propose efficient parallel algorithms on the EREW PRAM for optimally locating in a tree network a path-shaped facility and a tree-shaped facility of a specified length. Edges in the tree network have arbitrary positive lengths. Two optimization criteria are considered: minimum ecce

Parallel algorithm for the computation o

Parallel algorithm for the computation of characteristic polynomials of chemical graphs

✍ P. Venuvanalingam; P. Thangavel 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

A parallel algorithm is developed for the f i t time based on Frame's method to compute the characteristic polynomials of chemical graphs. This algorithm can handle all types of graphs: ordinary, weighted, directed, and signed. Our algorithm takes only linear time in the CRCW PRAM model with O(n9) p