On the complexity of finding multi-constrained spanning trees

DOI10.1016/0166-218X(83)90014-8MaRDI QIDQ1171508zbMATH OpenFDO

Authors Paolo M. Camerini, Giulia Galbiati, Francesco Maffioli

Publication date 1983

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(83)90014-8

zbMATH Keywords

classification of undirected spanning tree problemscomputational complexitymulti-constrained, unweighted caseundirected, unweighted graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Programming involving graphs or networks (90C35)

Cites work

• Complexity of spanning tree problems: Part I
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• The Bounded Path Tree Problem

Cited in

(17)

• A successful algorithm for the undirected Hamiltonian path problem
• Topological design of telecommunication networks --- local access design methods
• The image of weighted combinatorial problems
• On the approximability of some Maximum Spanning Tree Problems
• A new approach for the multiobjective minimum spanning tree
• In memoriam Paolo M. Camerini
• On some multicriteria arborescence problems: Complexity and algorithms
• Kruskal with embedded c-semirings to solve MST problems with partially-ordered costs
• A unifying model for locally constrained spanning tree problems
• An overview of graph covering and partitioning
• Spanning trees with minimum weighted degrees
• Heuristics with Constant Error Guarantees for the Multi Center Capacitated Minimum Spanning Tree Problem
• On the approximability of some maximum spanning tree problems
• scientific article; zbMATH DE number 2230227 (Why is no real title available?)
• Social distancing network creation
• Algorithms for 2-balanced connected k-partition problem in graphs
• Algorithms for 2-balanced connected \(k\)-partition problem in graphs

This page was built for publication: On the complexity of finding multi-constrained spanning trees

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