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

DOI10.18255/1818-1015-2021-1-22-37zbMATH Open1504.68077OpenAlexW3136380991MaRDI QIDQ5870845FDOQ5870845

Authors: A. V. 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

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

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Introduction to algorithms.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among combinatorial problems
• Title not available (Why is that?)
• Metagraphs and their applications.

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)