𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Optimal Parametric Search on Graphs of Bounded Tree-Width

✍ Scribed by David Fernández-Baca; Giora Slutzki

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
339 KB
Volume
22
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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

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

On the complexity of branch-and-bound se
On the complexity of branch-and-bound search for random trees
✍ Luc Devroye; Carlos Zamora-Cura 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 256 KB 👁 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co

On low bound of degree sequences of span
On low bound of degree sequences of spanning trees inK-edge-connected graphs
✍ Zhenhong, Liu; Baoguang, Xu 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 3 views

[•] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d k -tree, and α = 1 for k = 2, α = 2 for k ≥ 3.

Exact Values of N-Widths and Optimal Qua
Exact Values of N-Widths and Optimal Quadratures on Classes of Bounded Analytic and Harmonic Functions
✍ K.Y. Osipenko 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 419 KB

In this paper we find some exact values of \(n\)-widths in the integral metric with the Chebyshev weight function for the classes of functions that are bounded and analytic or harmonic in the interior of the ellipse with foci \(\pm 1\) and sum of semiaxes \(c\). We also construct optimal quadrature