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

DOI10.1142/S0129054123500235MaRDI QIDQ6629668

Fujita Satoshi

Publication date: 30 October 2024

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

zbMATH Keywords

approximation algorithmminimum spanning treeChristofides' algorithmbin packing algorithmminimum \(k\)-tree cover

Mathematics Subject Classification ID

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

Cites Work

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

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)