کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952328 | 1364440 | 2017 | 12 صفحه PDF | دانلود رایگان |
A dissociation set in a graph G=(V,E) is a vertex subset D such that the subgraph G[D] induced on D has vertex degree at most 1. A 3-path vertex cover in a graph is a vertex subset C such that every path of three vertices contains at least one vertex from C. A vertex set D is a dissociation set if and only if VâD is a 3-path vertex cover. There are many applications for dissociation sets and 3-path vertex covers. However, it is NP-hard to compute a dissociation set of maximum size or a 3-path vertex cover of minimum size in graphs. Several exact algorithms have been proposed for these two problems and they can be solved in Oâ(1.4658n) time in n-vertex graphs. In this paper, we reveal some interesting structural properties of the two problems, which allow us to solve them in Oâ(1.4656n) time and polynomial space or Oâ(1.3659n) time and exponential space.
Journal: Theoretical Computer Science - Volume 657, Part A, 2 January 2017, Pages 86-97