The computational complexity of Steiner tree problems in graded matrices

DOI10.1016/S0893-9659(97)00056-6zbMATH Open0891.05019MaRDI QIDQ1372300FDOQ1372300

Authors: Tibor Dudás, Bettina Klinz, Gerhard J. Woeginger 

Publication date: 9 December 1997

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Recommendations

• The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices
• The Steiner tree problem in Kalmanson matrices and in circulant matrices
• scientific article; zbMATH DE number 970831
• scientific article; zbMATH DE number 1532673

zbMATH Keywords

computational complexitySteiner tree problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Steiner tree problem
• The Complexity of Computing Steiner Minimal Trees

Cited In (4)

• K-center and K-median problems in graded distances
• Classes of directed graded graphs with polynomially solvable cardinality Steiner problem
• The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices
• The quadratic minimum spanning tree problem and its variations

This page was built for publication: The computational complexity of Steiner tree problems in graded matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1372300)