ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Sortierung

Digitale Medien

On complexity of subset interconnection designs (1995)

Du, Ding -Zhu ; Kelley, Dean F.

Springer

Journal of global optimization 6 (1995), S. 193-205

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1573-2916

Schlagwort(e): Subset interconnection design ; globally optimal ; polynomial time

Quelle: Springer Online Journal Archives 1860-2000

Thema: Mathematik

Notizen: Abstract Given a setX and subsetsX 1,...,X m, we consider the problem of finding a graphG with vertex setX and the minimum number of edges such that fori=1,...,m, the subgraphG i; induced byX i is connected. Suppose that for anyα pointsx 1,...,x α ε X, there are at mostβX i 's containing the set {x1,...,x α}. In the paper, we show that the problem is polynomial-time solvable for (α ⩽ 2,β ⩽ 2) and is NP-hard for (α⩾3,β=1), (α=l,β⩾6), and (α⩾2,β⩾3).

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1007/BF01096768

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer