✦ LIBER ✦

On scheduling send-graphs and receive-graphs under the LogP-model

✍ Scribed by W. Zimmermann; W. Löwe; D. Trystram

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 154 KB
Volume: 82
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(01)00257-5

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we consider scheduling of send-graphs (i.e., a root sends a message to all its leaves) and receive-graphs (i.e., a root receives messages from all its leaves) under the LogP-model. It turns out that even for these simple task-graphs it is NP-complete to decide whether there is a schedule under the LogP-model with makespan at most D for any fixed number of processors. We present approximation algorithms for these problems.

📜 SIMILAR VOLUMES

FMS scheduling based on timed Petri Net

FMS scheduling based on timed Petri Net model and reactive graph search

✍ Young Woo Kim; Tatsuya Suzuki; Tatsuo Narikiyo 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 540 KB

On the multiplication of divisions: The

On the multiplication of divisions: The use of graphs for sports scheduling

✍ D. de Werra 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 601 KB

Connectedness of digraphs and graphs und

Connectedness of digraphs and graphs under constraints on the conditional diameter

✍ X. Marcote; C. Balbuena; J. Fàbrega 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 206 KB

The Ising model and percolation on trees

The Ising model and percolation on trees and tree-like graphs

✍ Russell Lyons 📂 Article 📅 1989 🏛 Springer 🌐 English ⚖ 803 KB

Potts Model on Infinite Graphs and the L

Potts Model on Infinite Graphs and the Limit of Chromatic Polynomials

✍ Aldo Procacci; Benedetto Scoppola; Victor Gerasimov 📂 Article 📅 2003 🏛 Springer 🌐 English ⚖ 221 KB

On stability of Hamilton-connectedness u

On stability of Hamilton-connectedness under the 2-closure in claw-free graphs

✍ Zdeněk Ryjáček; Petr Vrána 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 269 KB 👁 1 views

We show that, in a claw-free graph, Hamilton-connectedness is preserved under the operation of local completion performed at a vertex with 2-connected neighborhood. This result proves a conjecture by Bollobás et al.