ZIB

Hits per page

hit 1 - 1 | 1 hit

Sorting

Electronic Resource

On complexity of subset interconnection designs (1995)

Du, Ding -Zhu ; Kelley, Dean F.

Springer

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

add to mindlist on the mindlist

Details

ISSN: 1573-2916

Keywords: Subset interconnection design ; globally optimal ; polynomial time

Source: Springer Online Journal Archives 1860-2000

Topics: Mathematics

Notes: 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).

Type of Medium: Electronic Resource

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

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit