Chitnis, Rajesh ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Misra, Pranabendu ; Ramanujan, M.S. ; Saurabh, Saket (2017) Faster exact algorithms for some terminal set problems Journal of Computer and System Sciences, 88 . pp. 195-207. ISSN 0022-0000
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.jcss.2017.04.003
Related URL: http://dx.doi.org/10.1016/j.jcss.2017.04.003
Abstract
Many problems on graphs can be expressed in the following language: given a graph G = (V, E) and a terminal set T ⊆ V , find a minimum size set S ⊆ V which intersects all “structures” (such as cycles or paths) passing through the vertices in T. We call this class of problems as terminal set problems. In this paper we introduce a general method to obtain faster exact exponential time algorithms for many terminal set problems.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 123406 |
| Deposited On: | 16 Sep 2021 06:55 |
| Last Modified: | 16 Sep 2021 06:55 |
Repository Staff Only: item control page
