Approximation algorithms for covering vertices by long paths

DOI10.1007/s00453-024-01242-3MaRDI QIDQ6586665

Mingyang Gong, Guohui Lin, Brett Edgar, Eiji Miyano, Jing Fan

Publication date: 13 August 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

approximation algorithm\(k\)-pathpath coveramortized analysislocal improvement

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• The two-equal-disjoint path cover problem of matching composition network
• Efficient bounds for the stable set, vertex cover and set packing problems
• \(k\)-path partitions in trees
• Approximation algorithms for two-machine flow-shop scheduling with a conflict graph
• Path cover problems with length cost
• A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
• Nontrivial path covers of graphs: existence, minimization and maximization
• A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem
• An improved approximation algorithm for the minimum 3-path partition problem
• The path partition problem and related problems in bipartite graphs
• 8/7-approximation algorithm for (1,2)-TSP
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
• STACS 2005
• A 21/16-Approximation for the Minimum 3-Path Partition Problem
• Path cover problems with length cost
• Approximation algorithms for the directed path partition problems

This page was built for publication: Approximation algorithms for covering vertices by long paths