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

DOI10.18255/1818-1015-2021-1-22-37zbMath1504.68077OpenAlexW3136380991MaRDI QIDQ5870845

Aleksandr Valer'Evich Smirnov

Publication date: 24 January 2023

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

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

zbMATH Keywords

NP-completenessspanning treeminimum spanning 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

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Metagraphs and their applications.
• Reducibility among Combinatorial Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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