Approximating minimum k-tree cover of a connected graph inspired by the multi-ferry routing in delay tolerant networks

DOI10.1142/S0129054123500235MaRDI QIDQ6629668FDO

Authors Fujita Satoshi

Publication date 30 October 2024

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

minimum spanning treeapproximation algorithmChristofides' algorithmbin packing algorithmminimum \(k\)-tree cover

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Theory of computing (68Qxx) Mathematical programming (90Cxx)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A (slightly) improved approximation algorithm for metric TSP
• A branch-and-bound algorithm for the mini-max spanning forest problem
• A heuristic algorithm for the mini-max spanning forest problem
• Approximation Algorithms for Min–Max Tree Partition
• Approximation algorithms for minimum tree partition
• Maximum matching and a polyhedron with 0,1-vertices
• On the complexity of graph tree partition problems.
• The Euclidean traveling salesman problem is NP-complete

This page was built for publication: Approximating minimum \(k\)-tree cover of a connected graph inspired by the multi-ferry routing in delay tolerant networks

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