NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3

DOI10.18255/1818-1015-2021-1-22-37MaRDI QIDQ5870845zbMATH OpenOpenAlexFDO

Authors A. V. Smirnov

Publication date 24 January 2023

Published in Modeling and Analysis of Information Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL http://mathnet.ru/eng/mais733

zbMATH Keywords

minimum spanning treeNP-completenessspanning treedivisible graphmultiple graphcomplete spanning treemultiple tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• Introduction to algorithms.
• Metagraphs and their applications.
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Reducibility among combinatorial problems

Cited in

(1)

• md-MST is NP-hard for \(d\geq 3\)

This page was built for publication: NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3

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