Área do cabeçalho
gov.br
Portal da UFC Acesso a informação da UFC Ouvidoria Conteúdo disponível em:PortuguêsEnglishEspañol
Brasão da Universidade Federal do Ceará

Universidade Federal do Ceará
Mestrado e Doutorado em Ciências da Computação

Área do conteúdo

Defesa de Proposta de Dissertação: Leonardo Cavalcante de Abreu

Data da publicação: 6 de novembro de 2024 Categoria: Notícias, Proposta de Dissertação

Título: Revisiting the Balanced Induced Subgraph Polytope

Data: 08/11/2024
Horário: 15h
Local: Sala de Reuniões do Bloco 910

 

Resumo:

A signed graph G is a graph associated with a sign function, which maps each edge of G to a positive or negative sign. Thus, the edge set E of G can be partitioned in two disjoint sets S and S, that correspond to the negative and positive edges of G, respectively. Multiple edges and loops are allowed. A signed graph is balanced if the vertex set V can be partitioned in U and U in such a way that all negative edges have one endpoint in U and the other one in U¯, and all positive edges have both endpoints in the same partition, that is there is no positive edge in the cut defined by U and U¯. The BALANCED INDUCED SUBGRAPH PROBLEM (BIS) consists in, given a signed graph G with a weight associated to each vertex, finding a balanced induced subgraph of G that maximizes the sum of weights of its vertices. The balanced induced subgraph polytope of G, namely PG, consists of the convex hull of its balanced induced subgraphs’ vertex-incidence vectors. Using an affine transformation from PG to a set covering polytope, we investigate relations between facets from one polytope to the other.

Banca examinadora:

  • Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC) – Orientador
  • Prof. Dr. Victor Almeida Campos (MDCC/UFC)
  • Prof. Dr. Márcio Costa Santos (UFMG)

 

 

Logotipo da Superintendência de Tecnologia da Informação
Acessar Ir para o topo