Determinação de conjuntos (0,2)-regulares em grafos e aplicações

• Autor(es): Pacheco, Maria F. ; Cardoso, Domingos Moreira ; Luz, Carlos J.
• Data: 2013
• Identificador Persistente: http://hdl.handle.net/10198/10672
• Origem: Biblioteca Digital do IPB
• Assunto(s): Emparelhamentos máximos; Programação convexa; Conjuntos (0,2)-regulares
• Tipo de Documento: Documento de conferência
• Idioma: Português

Descrição

Um conjunto (kappa,tau)-regular num grafo é um subconjunto de vértices que induz um subgrafo kappa-regular com a seguinte propriedade: cada vértice não pertencente ao conjunto tem nele exactamente tau vizinhos. Neste trabalho apresenta-se um novo algoritmo para a determinação de conjuntos (0,2)-regulares em grafos linha com a aplicação na determinação de emparelhamentos máximos em grafos com recurso à programação quadrática convexa.