Directed path partition problem on directed acyclic graphs

DOI10.1007/978-3-031-63021-7_24MaRDI QIDQ7021087zbMATH OpenFDO

Authors Hiroshi Eto, Shunsuke Kawaharada, Guohui Lin, Eiji Miyano, Tugce Ozdemir

Publication date 28 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-63021-7_24

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• \(k\)-path partitions in trees
• A 21/16-Approximation for the Minimum 3-Path Partition Problem
• A boundary class for the k-path partition problem
• A local search 4/3-approximation algorithm for the minimum 3-path partition problem
• Approximating the directed path partition problem
• Berge's conjecture on directed path partitions -- a survey
• Covering digraphs by paths
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Introduction to algorithms.
• Maximum skew-symmetric flows and matchings
• Planar Formulae and Their Uses
• Some optimal inapproximability results
• The path partition problem and related problems in bipartite graphs

Cited in

(3)

• Covering vertices by 4^+-paths: a simpler local search coupled with a more delicate amortization
• Path cover using only short paths
• TermiNet: a reinforcement learning framework for k-path partitioning problem

This page was built for publication: Directed path partition problem on directed acyclic graphs

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