Please use this identifier to cite or link to this item:
|Title:||The k-regular induced subgraph problem|
Haufmann, Torkel A.
Pinheiro, Sofia J.
|Keywords:||Regular induced graphs|
|Abstract:||We consider the problem of finding a maximum k-regular induced subgraph of a graph G. Theoretical results are established to compare upper bounds obtained from different techniques, including bounds from quadratic programming, Lagrangian relaxation and integer programming. This general problem includes well-known subproblems as particular cases of k. In this paper we focus on two particular cases. The case k=1 which is the maximal cardinality strong-matching and the case of finding the maximal cardinality family of induced cycles (k=2). For each one of the two cases, combinatorial algorithms are presented to solve the problem when graphs have particular structures and polyhedral descriptions of the convex hull of the corresponding feasible set are given. Computational tests are reported to compare the different upper bounds with the optimal values for different values of k, and to test the effectiveness of the inequalities introduced.|
|Appears in Collections:||CIDMA - Artigos|
OGTCG - Artigos
Files in This Item:
|1-s2.0-S0166218X17300665-main.pdf||Documento principal||482.15 kB||Adobe PDF||Request a copy|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.