Approximation algorithms for solving the heterogeneous rooted tree/path cover problems

DOI10.1007/S10878-025-01278-3MaRDI QIDQ6991815zbMATH OpenFDO

Authors Pengxiang Pan, Junran Lichen, Ping Yang, Jianping Li

Publication date 28 April 2025

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-025-01278-3

zbMATH Keywords

approximation algorithmscomplexity of algorithmsnonuniform speedsrooted tree/path cover

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites work

• 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem
• A (slightly) improved approximation algorithm for metric TSP
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• A primal-dual approximation algorithm for a two depot heterogeneous traveling salesman problem
• Algorithms and Computation
• An overview of graph covering and partitioning
• Approximation Algorithms for Min-Max Cycle Cover Problems
• Approximation hardness of min-max tree covers
• Better approximability results for min-max tree/cycle/path cover problems
• Capacitated vehicle routing with nonuniform speeds
• Combinatorial optimization. Theory and algorithms
• Matching, Euler tours and the Chinese postman
• Min-max cover of a graph with a small number of parts
• Min-Max Tours and Paths for Task Allocation to Heterogeneous Agents
• Min-max tree covers of graphs.
• Optimal coverage in wireless sensor networks
• The heterogeneous rooted tree cover problem
• The vehicle routing problem. Latest advances and new challenges.
• Vehicle Routing

This page was built for publication: Approximation algorithms for solving the heterogeneous rooted tree/path cover problems

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