TY - JOUR

T1 - The computational complexity of the k-minimum spanning tree problem in graded matrices

AU - Dudás, T.

AU - Klinz, B.

AU - Woeginger, G.J.

PY - 1998

Y1 - 1998

N2 - Given an undirected graph G = (V, E) where each edge e = (i, j) has a length dij = 0, the ¿-minimum spanning tree problem, ¿-MST for short, is to find a tree T in G which spans at least ¿ vertices and has minimum length l(T) = ¿(i,j)e Tdij. We investigate the computational complexity of the ¿-minimum spanning tree problem in complete graphs when the distance matrix D = (dij) is graded, i.e., has increasing, respectively, decreasing rows, or increasing, respectively, decreasing columns, or both. We exactly characterize polynomially solvable and NP-complete variants, and thus, establish a sharp borderline between easy and difficult cases of the ¿-MST problem on graded matrices. As a somewhat surprising result, we prove that the problem is polynomially solvable on graded matrices with decreasing rows, but NP-complete on graded matrices with increasing rows.

AB - Given an undirected graph G = (V, E) where each edge e = (i, j) has a length dij = 0, the ¿-minimum spanning tree problem, ¿-MST for short, is to find a tree T in G which spans at least ¿ vertices and has minimum length l(T) = ¿(i,j)e Tdij. We investigate the computational complexity of the ¿-minimum spanning tree problem in complete graphs when the distance matrix D = (dij) is graded, i.e., has increasing, respectively, decreasing rows, or increasing, respectively, decreasing columns, or both. We exactly characterize polynomially solvable and NP-complete variants, and thus, establish a sharp borderline between easy and difficult cases of the ¿-MST problem on graded matrices. As a somewhat surprising result, we prove that the problem is polynomially solvable on graded matrices with decreasing rows, but NP-complete on graded matrices with increasing rows.

U2 - 10.1016/S0898-1221(98)00150-3

DO - 10.1016/S0898-1221(98)00150-3

M3 - Article

VL - 36

SP - 61

EP - 67

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

SN - 0898-1221

IS - 5

ER -