A note on the complexity of the generalized minimum spanning tree problem

MaRDI QIDQ5309465zbMATH OpenFDO

Authors Petrica Pop, Corina Pop Sitar

Publication date 9 October 2007

zbMATH Keywords

\(\mathcal NP\)-hardcombinatorial optimization, complexity theorydynamic programminggeneralized minimum spanning tree problem

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On some polynomial solvable cases of the generalized minimum spanning tree problem
• New models of the generalized minimum spanning tree problem
• On the generalized minimum spanning tree problem
• A new relaxation method for the generalized minimum spanning tree problem
• scientific article; zbMATH DE number 1788251

Cited in

(12)

• Generalized spanning trees
• A two-level solution approach for solving the generalized minimum spanning tree problem
• The computational complexity of the k-minimum spanning tree problem in graded matrices
• On some polynomial solvable cases of the generalized minimum spanning tree problem
• scientific article; zbMATH DE number 2037815 (Why is no real title available?)
• A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
• scientific article; zbMATH DE number 2155132 (Why is no real title available?)
• scientific article; zbMATH DE number 4116325 (Why is no real title available?)
• scientific article; zbMATH DE number 2201897 (Why is no real title available?)
• scientific article; zbMATH DE number 5876375 (Why is no real title available?)
• Approximation theory in combinatorial optimization. Application to the generalized minimum spanning tree problem
• New models of the generalized minimum spanning tree problem

This page was built for publication: A note on the complexity of the generalized minimum spanning tree problem

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