.png){kind=icon}
.png){kind=icon}
Return
Maximum Path Sets in Trees
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-09524-4_15.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper proposes linear time algorithms for the Maximum Path Set (MPS) problem in undirected trees and arborescences. In the MPS problem, we are given a graph G = (V, E) and asked to find a maximum cardinality set of edges E' subset of E, such that G' = (V, E') is a collection of vertex-disjoint paths. The MPS problem finds applications in a number of logistics domains. In [3], it was shown that this problem is NP-complete in general graphs. This paper demonstrates that the MPS problem is solvable in linear time in undirected trees. Additionally, we reduce the MPS problem to the bb-matching problem, which in turn can be reduced to the Maximum Flow problem. From a polyhedral perspective, we design an integer program for the MPS problem in trees and prove that the constraint matrix of this formulation is totally unimodular. In other words, solving the linear programming relaxation provides an integral solution. We also design a linear time algorithm to solve the MPS problem in arborescences, which form a class of directed trees. Finally, we empirically analyze the various algorithms discussed in this paper.
Keywords:
Maximum Path Set
Linear time algorithm
Linear Program
Empirical Analysis
Journal
R
IF:
0
Papers:
18
Citations:
0