Please use this identifier to cite or link to this item:
Title: The k-regular induced subgraph problem
Author: Agra, Agostinho
Dahl, Geir
Haufmann, Torkel A.
Pinheiro, Sofia J.
Keywords: Regular induced graphs
Combinatorial optimization
Integer programming
Issue Date: 11-May-2017
Publisher: Elsevier
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.
Peer review: yes
DOI: 10.1016/j.dam.2017.01.029
ISSN: 0166-218X
Appears in Collections:CIDMA - Artigos
OGTCG - Artigos

Files in This Item:
File Description SizeFormat 
1-s2.0-S0166218X17300665-main.pdfDocumento principal482.15 kBAdobe PDFrestrictedAccess

Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.