Amini, Omid ; Sau, Ignasi ; Saurabh, Saket (2012) Parameterized complexity of finding small degree-constrained subgraphs Journal of Discrete Algorithms, 10 . pp. 70-83. ISSN 1570-8667
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.jda.2011.05.001
Related URL: http://dx.doi.org/10.1016/j.jda.2011.05.001
Abstract
In this article we study the parameterized complexity of problems consisting in finding degree-constrained subgraphs, taking as the parameter the number of vertices of the desired subgraph. Namely, given two positive integers d and k, we study the problem of finding a d-regular (induced or not) subgraph with at most k vertices and the problem of finding a subgraph with at most k vertices and of minimum degree at least d. The latter problem is a natural parameterization of the d-girth of a graph (the minimum order of an induced subgraph of minimum degree at least d).
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 123458 |
| Deposited On: | 20 Sep 2021 07:59 |
| Last Modified: | 20 Sep 2021 07:59 |
Repository Staff Only: item control page
