✦ LIBER ✦

Greedy packing and series-parallel graphs

✍ Scribed by Alan J Hoffman; Alan C Tucker

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 471 KB
Volume: 47
Category: Article
ISSN: 0097-3165
DOI: 10.1016/0097-3165(88)90039-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On greedy algorithms for series parallel

On greedy algorithms for series parallel graphs

✍ Alan J. Hoffman 📂 Article 📅 1988 🏛 Springer-Verlag 🌐 English ⚖ 304 KB

Equistable series–parallel graphs

✍ Ephraim Korach; Uri N. Peled 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 163 KB

A graph is called equistable when there is a non-negative weight function on its vertices such that a set S of vertices has total weight 1 if and only if S is maximal stable. We characterize those series-parallel graphs that are equistable, generalizing results of Mahadev et al. about equistable out

Series parallel composition of greedy li

Series parallel composition of greedy linear programming problems

✍ Wolfgang W. Bein; Peter Brucker; Alan J. Hoffman 📂 Article 📅 1993 🏛 Springer-Verlag 🌐 English ⚖ 612 KB

Chromaticity of series-parallel graphs

✍ K.M. Koh; C.P. Teo 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 454 KB

By applying a sequence of edge-gluings on a set of cycles each of length k, we obtain a special series-parallel graph. The well-known k-gon tree theorem (see [l, lo]) states that these graphs form a X-equivalence class. Many of the other known classes of X-unique graphs and X-equivalence classes are

Asymptotic packing and the random greedy

Asymptotic packing and the random greedy algorithm

✍ Vojtěch Rödl; Luboš Thoma 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 593 KB

Let H be an r-uniform hypergraph satisfying deg(x) = D(l + o( 1)) for each vertex x E V ( H ) and deg(x, y) = o ( D ) for each pair of vertices x, y E V ( H ) , where D+=. Recently, J . Spencer [5] showed, using a branching process approach, that almost surely the random greedy algorithm finds a pac

Series-parallel graphs: A logical approa

Series-parallel graphs: A logical approach

✍ T. A. McKee 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 297 KB

The notions "series-parallel" and "nonseparable" are shown to be logical converses of each other when formulated in a particular dual-like fashion. Self-dual circuitkutset characterizations are given of series-parallel and of series-parallel nonseparable graphs.