✦ LIBER ✦

A short note on the approximability of the maximum leaves spanning tree problem

✍ Scribed by G. Galbiati; F. Maffioli; A. Morzenti

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 354 KB
Volume: 52
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(94)90139-2

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the approximability of some maximum s

On the approximability of some maximum spanning tree problems

✍ Giulia Galbiati; Angelo Morzenti; Francesco Maffioli 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 844 KB

We study the approximability of some problems which aim at finding spanning trees in undirected graphs which maximize, rather than minimize, a single objective function representing a form of benefit or usefulness of the tree. We prove that the problem of finding a spanning tree which maximizes the

On the approximability of the Steiner tr

On the approximability of the Steiner tree problem

✍ Martin Thimm 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 165 KB

We show that it is not possible to approximate the minimum Steiner tree problem within 1 + 1 162 unless RP = NP. The currently best known lower bound is 1 + 1 400 . The reduction is from H astad's nonapproximability result for maximum satisÿability of linear equation modulo 2. The improvement on the

A note on the minimum label spanning tre

A note on the minimum label spanning tree

✍ Yingyu Wan; Guoliang Chen; Yinlong Xu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 44 KB

We give a tight analysis of the greedy algorithm introduced by Krumke and Wirth for the minimum label spanning tree problem. The algorithm is shown to be a (ln(n -1) + 1)-approximation for any graph with n nodes (n > 1), which improves the known performance guarantee 2 ln n + 1.

The minimum spanning tree problem on a p

The minimum spanning tree problem on a planar graph

✍ Tomomi Matsui 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 301 KB

On the value of a random minimum spannin

On the value of a random minimum spanning tree problem

✍ A.M. Frieze 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 324 KB

On graphs with the maximum number of spa

On graphs with the maximum number of spanning trees

✍ Alexander K. Kelmans 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 814 KB

Let 3:; denote the set of simple graphs with n vertices and m edges, t ( G ) the number of spanning trees of a graph G , and F 2 H if t(K,\E(F))?t(K,\E(H)) for every s? max{u(F), u ( H ) } . We give a complete characterization of >-maximal (maximum) graphs in 3:; subject to m 5 n . This result conta